题解 [六省联考2017]摧毁“树状图”

· · 题解

题目链接

这里提供一种换根dp的做法，可能比前面那些题解里面讲的做法容易实现且不难调试？（雾

题意：求树上两条不相交的路径（指的是没有边重合），使得删去路径上的边和点后剩下的联通块数量尽可能多。

不妨按树上两条路径的相对情况来分类讨论：

情况一：两条路径存在点重合。

因为树上两个点之间只有一条路径，所以如果有点重合，那么一定只会有一个点是公共点，我们可以把这一个点单独拎出来作为根，不难发现所谓的两条路径可以视为 1\sim 4 条链，其中链的一端就是根，只需要记录从根连出去的前四大链即可得到这种情况的答案。

情况二：两条路径不存在点重合。

不难发现必然存在一棵子树使得一条路径完全在这棵子树内而另外一条路径和这个子树没有交点，考虑枚举每一棵子树，规定这棵子树内的路径经过子树的根，然后找到在这棵子树内的最优路径和子树外的最优路径。

不难发现，上面列出来所要求的都可以通过换根较容易地求出。

状态如下（以下所说的路径及链都可以退化为单点）：

设 mx(u,k) 表示考虑在以 u 为根的子树中，对于所有 u 的儿子 v 中 dp(v) 第 k+1 大的值。

设 cnt(u) 表示 u 的儿子数量。

设 dp(u) 表示考虑在以 u 为根的子树中，去掉以 u 为一个端点的链后剩下的联通块数量的最大值。

设 fp(u) 表示考虑在以 u 为根的子树中，去掉经过 u 点的某条路径后剩下的联通块数量的最大值。

设 f(u) 表示考虑在以 u 为根的子树中，去掉某条路径后剩下的联通块数量的最大值。

转移如下：

dp(u)=\max(cnt(u),mx(u,0)+cnt(u)-1) fp(u)=\max(dp(u),mx(u,0)+mx(u,1)+cnt(u)-2)

发现 f(u) 可能不太好转移，因为对于 u 的儿子 v 里面的一条路径，如果是经过 v 点的话，只考虑以 v 为根的子树是不会考虑到 v 外面连着的 u 所在的连通块造成的贡献，而如果不经过 v 点的话， u 所在的连通块是不会造成贡献的，所以考虑多记录点东西：

设 f_0(u) 表示考虑在以 u 为根的子树中，去掉某条路径后剩下的联通块数量的最大值；设 f_1(u) 表示认为删去 u 点后 u 外面还有一个连通块，去掉某条路径后剩下的连通块数量的最大值。

然后我们再假设 fmx(u) 表示对于所有 u 的儿子 v 中 f_1(v) 的最大值。

转移就比较容易了：

f_0(u)=\max(fmx(u),fp(u)) f_1(u)=\max(fmx(u),fp(u)+1)

好的，看看我们转移用到了哪些东西： fmx(u) 、 mx(u,0) 以及 mx(u,0)+mx(u,1) 。

显然，换根的时候只要记录： fmx(u) 的最大次大， mx(u,0) 的最大次大次次大。

不难发现，其实我们更新答案的时候要用到 mx(u,0\sim 3) ，所以 mx(u,0) 其实要记录前四大。

于是就可以愉快地写代码了：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 500000000
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
    int f;char c;
    for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
    static char q[64];int cnt=0;
    if(!x)pc('0');if(x<0)pc('-'),x=-x;
    while(x)q[cnt++]=x%10+'0',x/=10;
    while(cnt--)pc(q[cnt]);
}
const int maxn=100005;
struct Edge{
    int v,nt;
    Edge(int v=0,int nt=0):
        v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
    e[++num]=Edge(v,hd[u]);hd[u]=num;
}
int mx[maxn][4],fmx[maxn][2];
void change(int x,int val){
    for(int i=0;i<4;++i)
        if(mx[x][i]<val)
            mx[x][i]^=val^=mx[x][i]^=val;
}
void fchange(int x,int val){
    for(int i=0;i<2;++i)
        if(fmx[x][i]<val)
            fmx[x][i]^=val^=fmx[x][i]^=val;
}
int dp[maxn],f[maxn][2],fp[maxn];
void dfs0(int u,int fa){
    int cnt=0;
    mx[u][0]=mx[u][1]=mx[u][2]=mx[u][3]=-inf;
    dp[u]=f[u][0]=f[u][1]=fmx[u][0]=fmx[u][1]=-inf;
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==fa)continue;
        dfs0(v,u);++cnt;
        change(u,dp[v]);
        fchange(u,f[v][1]);
    }
    dp[u]=max(cnt,mx[u][0]+cnt-1);
    fp[u]=max(dp[u],mx[u][0]+mx[u][1]+cnt-2);
    f[u][0]=max(fmx[u][0],fp[u]);
    f[u][1]=max(fmx[u][0],fp[u]+1);
}
int ans,d[maxn];
void dfs1(int u,int fa){
    int sm=d[u];ans=max(ans,d[u]);
    for(int i=0;i<4;++i)
        ans=max(ans,sm+=mx[u][i]-1);
    int cnt=d[u]-1;
    for(int i=hd[u];i;i=e[i].nt){
        int v=e[i].v;
        if(v==fa)continue;
        int t=-1;
        for(int j=0;j<4;++j)
            if(mx[u][j]==dp[v])
                t=j;
        int mx0=mx[u][0],mx1=mx[u][0]+mx[u][1],mx2=fmx[u][0];
        if(t==0)mx0=mx[u][1],mx1=mx[u][1]+mx[u][2];
        else if(t==1)mx1=mx[u][0]+mx[u][2];
        if(fmx[u][0]==f[v][1])mx2=fmx[u][1];
        dp[u]=max(cnt,mx0+cnt-1);
        fp[u]=max(dp[u],mx1+cnt-2);
        f[u][0]=max(mx2,fp[u]);
        f[u][1]=max(mx2,fp[u]+1);
        ans=max(ans,f[u][0]+fp[v]);
        change(v,dp[u]);fchange(v,f[u][1]);
        dfs1(v,u);
    }
}
int main(){
    int T,x;
    read(T),read(x);
    while(T--){
        int n,tmp;
        read(n);
        for(int i=0;i<x;++i)
            read(tmp),read(tmp);
        num=0;
        for(int i=1;i<=n;++i)
            hd[i]=d[i]=0;
        for(int i=1;i<n;++i){
            int u,v;
            read(u),read(v);
            qwq(u,v);qwq(v,u);
            ++d[u],++d[v];
        }
        ans=0;
        dfs0(1,0);dfs1(1,0);
        write(ans),pc('\n');
    }
    return 0;
}

成功降低了思维及讨论难度，为何不写换根呢？