题解 P1395 【会议】

· · 题解

现在的几篇题解好像都有点过于抽象，我来发布一篇容易懂的题解.

首先，阅读题目可以看出来，这道题目实际上就是求树的重心，那么我们的思路就转化为：在 O(n) 内先求出树的重心，再用 dfs 求出到重心的距离之和。

树的重心：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。

我们先设任意一个点为树的根（比如 1 号节点），这样就把这棵树变成了有根树。考虑以 i 为根的最大子树的节点数，设为 g[i] ， i 的所有子节点的集合为 S ，则有

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~g[i]=\sum(s[j]+1)~,~ j∈S

其中上面的 +1 指子节点本身。显然可以用一遍 dfs 求出所有的 g[i] 。

接下来我们设立一个数组 f[i] ，表示以 i 为根的最大子树的节点数。

如果当前节点 i 是根节点，显然有

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~f[i]=\max(g[j])~,~j∈S

如果 i 不是根节点，那么对于 i 的所有子树，必然也满足上述等式。此外，我们还要考虑 i 的父节点，也就是当 i 成为根时，其父节点变成子节点后的节点数。

回归当前以 1 为根的情况，设 T 不包括节点 i 及 i 子树的其余节点的集合，那么可以判断出

且 $~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~T~∩~\{i\}=T~∩~S=\{i\}~∩~S=~\varnothing

用 |S| 表示集合 S 中的元素的个数，则

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|T|=|U|-|S|-|\{i\}| ∴ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~f[i]=n-g[i]-1

显然 f[i] 可以在求 g[i] 的 dfs 中求出。那么树的重心就是 f[i]_{min} 时的 i 值。

此外，所有点到 i 点的距离之和在数值上等于以 i 为根的所有子树的节点数， ∴ 可以调用相同的 dfs 函数求出距离。

Code

#include "bits/stdc++.h"
#define N 1000001
using namespace std;

int n,u,v,O,vis[N],f[N],g[N],ans;
int k,b[N],first[N],next[N],last[N];//f[i]:以i为根的最大子树的节点数
                                    //g[i]:以i为根的子树的节点个数
void add(int x,int y)
{
    k++;
    b[k]=y;
    if(first[x]==0)
        first[x]=k;
    else
        next[last[x]]=k;
    last[x]=k;
}

void dfs(int x)
{
    vis[x]=1;
    int p=first[x];
    while(p)
    {
        if(!vis[b[p]])
        {
            dfs(b[p]);
            g[x]+=g[b[p]]+1;
            f[x]=max(f[x],g[b[p]]+1);
        }
        p=next[p];
    }
    f[x]=max(f[x],n-g[x]-1);
    vis[x]=0;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1);
    f[0]=INT_MAX;
    for(int i=1;i<=n;i++)
        if(f[O]>f[i])
            O=i;//树的重心可以有多个,这里取编号最小的一个
    printf("%d ",O);
    memset(g,0,sizeof(g));
    dfs(O);
    for(int i=1;i<=n;i++)
        ans+=g[i];
    printf("%d",ans);
    return 0;
}