P3478 题解

__vector__ · 2022-08-31 23:19:36 · 个人记录

做法

dfs 每个点作为根，计算答案。

dfs 时，设当前点是 u，转移到其子节点 v 时，考虑一下答案变化：

以 v 为根节点的子树所有节点深度减一。

所有不在 v 的子树的节点深度加一。

所以预处理每个节点子树的大小，然后 dfs 转移就行。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int n;
int head[maxn];
struct EDGE
{
    int to,nxt;
}edge[maxn<<1];
int cnt;
inline void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int size[maxn];
void dfs(int u,int _fa)
{
    size[u]++;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        dfs(to,u);
        size[u]+=size[to];
    }
}
ll f[maxn];
void redfs(int u,int _fa)
{
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(to==_fa)continue;
        f[to]=f[u]+ll(n-2*size[to]);
        redfs(to,u);
    }
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    {
        f[1]+=(ll)size[i];
    }
    redfs(1,0);
    ll ans=0;
    int out=1;
    for(int i=1;i<=n;i++)
    {
        if(f[i]>ans)
        {
            ans=f[i];
            out=i;
        }
    }
    printf("%d",out);
    return 0;
}