【题解】[POI2015] MOD -526互联

挺恶心的感觉这题代码，就来写写题解。

题目分析

假设我们现在要删掉 \((x,y)\) 这条边，思考这样能贡献的最大或最小直径。

不难发现，此时一棵树分裂成了两棵树 \(a,b\)，我们令它们的直径分别为 \(la,lb\)。将两棵树内直径的任意端点连起来，发现 \(maxi=la+lb+1\)。将两棵树内直径的中点连起来，发现 \(mini=\left\lceil\dfrac{la}{2}\right\rceil+\left\lceil\dfrac{lb}{2}\right\rceil+1\)。所以我们的目标就是维护这两个值。

假装现在的根节点是 \(1\)（其实是谁大概都无所谓），再考虑维护这两个值，也就是要维护 \(dp[x]\) 表示在 \(x\) 的子树内的直径，\(del[x]\) 表示删掉 \(x\) 和 \(fa[x]\) 这条边后在 \(x\) 的子树外的直径。分别考虑怎么维护。

\(dp[x]\) 的维护可以套路地想到维护 \(chain\_down[x][0/1]\) 表示在 \(x\) 的子树内的最长链和次长链。

\(del[x]\) 的维护是个难点。我们考虑维护 \(chain\_up[x]\) 表示从 \(x\) 开始向上的最长链。发现如果删掉了 \(x\)，那么 \(del[x]\) 可能会有以下几种情况（\(fx\) 为 \(x\) 的父亲）：

是 \(dp[fx]\)，也就是 \(chain\_down[fx][0]+chain\_down[fx][1]\)。但此时要满足子树 \(x\) 不是 \(fx\) 的最长链或者次长链，所以我们还要维护一个次次长链，分类讨论一下即可。所以次次长链加最长链什么的情况都放在这一种情况内了。
是 \(chain\_up[fx]+chain\_down[fx][0]\)，因为此时类似于是以 \(fx\) 为一个根节点嘛，所以就找外面的一条链和里面的一条链即可。特判一下 \(x\) 就是最长链的情况，这时候是加上次长链。
是 \(fx\) 的一个子节点内的直径。此时也要判断一下 \(x\) 是不是这个直径最长的子节点，所以我们还需要维护一个 \(dia[fx][0/1]\) 维护在 \(x\) 的子节点的子树内的最长直径和次长直径。

现在我们明确了要维护哪些值，然后再考虑怎么维护。

我们发现 \(fa[x],chain\_down[x][0/1/2],dia[x][0/1]\) 的处理不需要依赖其他数组，我们就可以在第一遍 dfs 内维护这些值。

感觉这题理解哪些数组是干什么的很重要，所以我再重新列一下好了（

\(fa[x]\)：\(x\) 的父亲
\(deep[x]\)：\(x\) 的深度（后面有用）
\(chain_up[x]\)：从 \(x\) 开始向上的最长链
\(chain_down[x][0/1/2]\)：在 \(x\) 的子树内的最长链，次长链和次次长链
\(del[x]\)：删掉 \(x\) 和 \(fx\) 这条边后在 \(x\) 的子树外的直径
\(dia[x][0/1]\)：在 \(x\) 的子节点的子树内的最长直径和次长直径
\(dp[x]\)：在 \(x\) 的子树内的直径

void dfs1(int x,int fx){
    deep[x]=deep[fx]+1;
    fa[x]=fx;
    for(int i=head[x];i;i=edge[i].nex){
        int v=edge[i].to;
    //    chain_up[v]=chain_up[x]+1;
        if(v==fx) continue;
        dfs1(v,x);
        dp[x]=max(dp[x],dp[v]);

        int now=chain_down[v][0]+1;
        if(now>chain_down[x][0]){
            chain_down[x][2]=chain_down[x][1];
            chain_down[x][1]=chain_down[x][0];
            chain_down[x][0]=now;
        }
        else if(now>chain_down[x][1]){
            chain_down[x][2]=chain_down[x][1];
            chain_down[x][1]=now;
        }
        else if(now>chain_down[x][2])
            chain_down[x][2]=now;

        now=dp[v];
        if(now>dia[x][0]){
            dia[x][1]=dia[x][0];
            dia[x][0]=now;
        }
        else if(now>dia[x][1])
            dia[x][1]=now;
    }
    dp[x]=max(dp[x],chain_down[x][0]+chain_down[x][1]);
}

剩下的数组在第二次 dfs 内处理

void dfs2(int x,int fx){
    if(fx){
        int now=dp[x]+del[x]+1;
        if(maxi.v<now){
            maxi.v=now;
            maxi.xa=x,maxi.ya=fx;
        }
        now=max(max(del[x],dp[x]),(1+del[x])/2+(1+dp[x])/2+1);
        if(mini.v>now){
            mini.v=now;
            mini.xa=x,mini.ya=fx;
        }
    }

    for(int i=head[x];i;i=edge[i].nex){//删掉v这个点
        int v=edge[i].to;
        if(v==fx) continue;
        chain_up[v]=chain_up[x]+1;
        del[v]=del[x];

        int now=chain_down[v][0]+1;
        if(now==chain_down[x][0]){
            del[v]=max(del[v],max(chain_down[x][1]+chain_down[x][2],chain_up[x]+chain_down[x][1]));
            chain_up[v]=max(chain_up[v],chain_down[x][1]+1);
        }
        else if(now==chain_down[x][1]){
            del[v]=max(del[v],max(chain_down[x][0]+chain_down[x][2],chain_up[x]+chain_down[x][0]));
            chain_up[v]=max(chain_up[v],chain_down[x][0]+1);
        }
        else{
            del[v]=max(del[v],max(chain_down[x][0]+chain_down[x][1],chain_up[x]+chain_down[x][0]));
            chain_up[v]=max(chain_up[v],chain_down[x][0]+1);
        }
        now=dp[v];
        if(now==dia[x][0])
            del[v]=max(del[v],dia[x][1]);
        else
            del[v]=max(del[v],dia[x][0]);

        dfs2(v,x);
    }
}

现在我们求出了最大直径和得到它需要删哪两个节点，最小直径和得到它需要删哪两个节点。接下来就要求要接哪两个节点。

先考虑最小直径的，之前分析的是两条直径的中点。所以我们可以分别求两遍 dfs 求出两条直径的端点，再暴力求出中点即可。

再考虑最大直径的，这个比最小直径好处理，随便跑下 dfs 找到一个端点即可。