树形dp换根，求切断任意边形成的两个子树的直径—

换根dp就是先任取一点为根，预处理出一些信息，然后在第二次dfs过程中进行状态的转移处理

本题难点在于任意割断一条边，求出剩下两棵子树的直径：

　　设割断的边为（u，v）,设down[v]为以v为根的子树的直径长度，up[v]为u所在的子树的直径长度，那么down[v]就是很常规的子树直径的换根dp的求法，up[v]则要通过分情况讨论

　　第一种情况，组成up[v]的两条链，一条是u上方的链，一条是u下方且不属于子树v的链

　　第二种情况，组成up[v]的两条链都是u下方且不属于子树v的链

那么换根的过程中就要考虑这两种情况，我们必须维护u下的前三条最长的链，和u上一条最长的链，

因为如果v刚好在u深度最大的子树里，考虑第二种情况的up[v]时就要用到u下次长，次次长的链，而考虑第一种情况时就必须要用到u上的最长链，所以最少需要维护u下三条链+u上一条链

切断任意一条边，求剩下两个子树的直径
换根dp，第一次dfs预先处理出的数据dp[u][0|1|2]表示u的最长|次长|次次长链
down[u]表示u子树里的最长链长度

第二次dfs求出
len[u][0|1]表示u子树里的不经过u的最长|次长链
枚举每个儿子v，
求出dp[v][3]表示v上面的最长链
up[v]表示切断(u，v)后，u所在块的最长链
那么切断(u,v)后，两个子树的直径就是down[v],up[v]
down[v]好求，up[v]要通过u来求出

换根的过程：从u换到v时，up[v]有两种情况，一种是一条u的上面+一条u的下面，另一种是两条u的下面

#include<bits/stdc++.h>

#include<vector>

using namespace std;

#define N 200005

vector<int>G[N];

int n,u[N],v[N],a[N],down[N],up[N],dp[N][],len[N][],d[N];

void dfs1(int u,int pre,int dep){

    d[u]=dep;

    for(int i=;i<G[u].size();i++){

        int v=G[u][i];

        if(v==pre)continue;

        dfs1(v,u,dep+);

        int tmp=dp[v][]+;

        if(tmp>dp[u][])swap(dp[u][],tmp);

        if(tmp>dp[u][])swap(dp[u][],tmp);

        if(tmp>dp[u][])swap(dp[u][],tmp);

        down[u]=max(down[u],down[v]);

    }

    down[u]=max(down[u],dp[u][]+dp[u][]);

}

void dfs2(int u,int pre){

    for(int i=;i<G[u].size();i++){//求出u下不经过u的最长|次长 链

        int v=G[u][i];

        if(v==pre)continue;

        int tmp=down[v];

        if(tmp>len[u][])swap(tmp,len[u][]);

        if(tmp>len[u][])swap(tmp,len[u][]);

    }

    for(int i=;i<G[u].size();i++){//边(u,v)将原树分成两棵子树

        int v=G[u][i];

        if(v==pre)continue;

        //原树删掉v子树后，求v上的最长链dp[v][3]，同时求出第一种情况的up[v]

        if(dp[u][]==dp[v][]+){//v是u的最深子树

            dp[v][]=max(dp[u][],dp[u][])+;

            up[v]=max(dp[u][],dp[u][])+dp[u][];

        }

        else if(dp[u][]==dp[v][]+){//v是u的次深子树

            dp[v][]=max(dp[u][],dp[u][])+;

            up[v]=max(dp[u][],dp[u][])+dp[u][];

        }

        else {//v是u的其他子树

            dp[v][]=max(dp[u][],dp[u][])+;

            up[v]=max(dp[u][],dp[u][])+dp[u][];

        }

        //求第二种情况的up[v],也要特别判一下v子树里是否有u下的最长链

        if(len[u][]==down[v])up[v]=max(up[v],len[u][]);

        else up[v]=max(up[v],len[u][]);

        dfs2(v,u);

    }

}

void init(){

    memset(dp,,sizeof dp);

    memset(a,,sizeof a);

    memset(len,,sizeof len);

    memset(down,,sizeof down);

    memset(up,,sizeof up);

    for(int i=;i<=n;i++)G[i].clear();

}

int main(){

    int t;cin>>t;while(t--){

        init();cin>>n;

        for(int i=;i<n;i++){

            scanf("%d%d",&u[i],&v[i]);

            G[u[i]].push_back(v[i]);

            G[v[i]].push_back(u[i]);

        }

        dfs1(,,);

        dfs2(,);

        for(int i=;i<n;i++){

            int x=u[i],y=v[i];

            if(d[x]<d[y])swap(x,y);

            a[up[x]+]=max(a[up[x]+],down[x]+);

            a[down[x]+]=max(a[down[x]+],up[x]+);

        }

        long long ans=;

        for(int i=n;i>=;i--){

            a[i]=max(a[i],a[i+]);

            ans+=a[i];

        }

        cout<<ans<<'\n';

    }

}

巴特西

树形dp换根，求切断任意边形成的两个子树的直径——hdu6686

最新文章

热门文章