平衡树解题报告

Description

小D最近又在种树，可是他的种树技巧还是很差，种出的树都长的歪七扭八，为了让树变得平衡一些，小D决定从树上删掉一条边，然后再加上一条边，使得到的仍然是一棵树并且这棵树的直径（树上最远两点距离）尽量小。请你求出新树的最小直径长度。每条边的长度均为1。

Input Format

第一行一个正整数n，表示树上节点个数。第2~n行每行两个正整数x,y，表示x到y之间有一条边。

Output Format

输出一个整数，表示答案。

Sample Input

4
1 2
2 3
3 4

Sample Output

2

Hint

【数据范围】
对于数据点1~2，n<=50；
对于数据点3~4，n<=5,000；
对于数据点5~6，第i条给出的边为i到i+1的边；
对于全部数据（1~10），n<=500,000。

Solution

本题有个很直观的想法，就是枚举每一条边把它删除后再连接某对点，然后求直径
更新答案。问题是删除这条边后得到两棵树，连接这两棵树的哪对点会使直径最小呢？
(当然你也可以暴力枚举)可以证明连接两棵树的中点是最优的。

树的中心：找到一个点使得以该点为根树的深度最小（等价于找到一个点使得以该点为起点的最长的路径最短）。
证明：设我们连接的点对为(u,v)。

两棵树合并成一棵树的直径有两种情况，1.直径存在这两棵树之间，2.直径是一条经过这两棵树的路径，对于第一种情况我们无法改变（因为这两棵树已经固定了），我们能做的是让经过这两棵树的最长路径L最短，容易想到|L|其实等于以u为起点的最长路径的长度加上以v为起点的最长路径的长度加1，而使以这两个点为起点的最长路径最短的点其实就是树的中心，所以连接两棵树的中心能使情况2最小，故连接两棵树的中心是最优的。

以中点为起点的最长路径的长度=ceil(d+1) (d是树的直径)

经过以上分析，我们要做的就是时刻维护每条边删除后出现的两棵树的直径，这很容易用树形DP维护。

Code

#include<cstdio>
#include<algorithm>
#define N 500007
using namespace std;

inline int read(){
    int num=0,k=1;char c=getchar();
    while (c<'0'||c>'9'){if (c=='-')k=-1;c=getchar();}
    while (c>='0'&&c<='9')num=(num<<1)+(num<<3)+c-48,c=getchar();
    return num*k;
}

struct info{
    int to,pre;
}edge[2*N];

int ans,n,size,head[N];
int fa[N],sonD[2][N],maxD[N],Down[3][N];

inline int Adl(int u,int v){
    edge[++size].pre=head[u];
    edge[size].to=v;
    head[u]=size;
}

inline void dfs1(int k){
    for (int i=head[k];i;i=edge[i].pre){
        int t=edge[i].to;
        if (t==fa[k]) continue;
        fa[t]=k;
        dfs1(t);
        if (Down[0][t]+1>Down[0][k]){
            Down[2][k]=Down[1][k];
            Down[1][k]=Down[0][k];
            Down[0][k]=Down[0][t]+1;
        }
        else if (Down[0][t]+1>Down[1][k])
            Down[2][k]=Down[1][k],Down[1][k]=Down[0][t]+1;
        else if (Down[0][t]+1>Down[2][k])
            Down[2][k]=Down[0][t]+1;
        if (maxD[t]>sonD[0][k]){
            sonD[1][k]=sonD[0][k];
            sonD[0][k]=maxD[t];
        }
        else if (maxD[t]>sonD[1][k])
            sonD[1][k]=maxD[t];
        maxD[k]=max(maxD[k],maxD[t]);
    }
    maxD[k]=max(maxD[k],Down[1][k]+Down[0][k]);
}

inline void dfs2(int k,int l,int D){
    if (k!=1)
     ans=min(ans,max((maxD[k]+1)/2+(D+1)/2+1,max(D,maxD[k])));
    for (int i=head[k];i;i=edge[i].pre){
        int t=edge[i].to,len,d;
        if (t==fa[k]) continue;
        if (Down[0][t]+1!=Down[0][k])
         len=Down[0][k];
        else len=Down[1][k];
        if (maxD[t]!=sonD[0][k]) d=sonD[0][k];
        else d=sonD[1][k];
        d=max(d,max(D,len+l));
        if (Down[0][t]+1==Down[0][k])
          d=max(d,Down[1][k]+Down[2][k]);
         else if (Down[0][t]+1==Down[1][k]) 
           d=max(d,Down[0][k]+Down[2][k]);
          else 
           d=max(d,Down[0][k]+Down[1][k]);
        len=max(len,l)+1;
        dfs2(t,len,d);
    }
}

bool List;

int main(){
    n=read();List=true;
    for (int i=1;i<n;++i){
        int u,v;
        u=read(),v=read();
        Adl(u,v),Adl(v,u);
        if (u!=i||v!=i+1) List=false;
    }
    ans=n;
    if (List)
        for (int i=1;i<=n;++i) ans=min(ans,(n-i)/2+i);
    else {
        dfs1(1);
        dfs2(1,0,0);
    }
    printf("%d",ans);
}

秒客网

【NOIP2017模拟测试（10-28）】平衡树