链接：https://ac.nowcoder.com/acm/problem/201400

题意: 给出连通图，由n个点和n-1条边构成，在树上选择一个结点作为根，使得以这个结点为根的所有结点的深度和最小。默认根的深度为0

样例：
4
1 2
1 3
1 4

很显然以1为根,depth=1+1+1=3 是最小的
如图所示：
图片说明

现在我们要开始换根了！

遍历1这个结点的儿子2，3，4

我们以3这个结点为例

换好根的结果如下图所示:
图片说明

设 f[u]表示以u为根节点,所有点深度和
设 dep[N];//dep[u]表示节点u的深度
设 cnt[N];//cnt[u]表示节点u下的儿子个数,包含它本身

f[v]=f[u]-cnt[v]+(n-cnt[v]); //转移方程
当前结点v，f[v]=父亲结点的答案f[u]-这个结点的儿子数cntv+剩余结点的个数(n-cnt[v])(相当于上图除3号结点，剩余1，2，4结点的深度都是要加1)

怎么求dep数组呢，dfs一遍，当前节点的深度=父节点的深度+1即可

怎么求cnt数组呢，dfs一遍，在回溯的时候，向上合并答案，也就说父节点的个数等于下面所以儿子的个数之和，我们得从下往上计算。

最后答案的话，很简单，只要拿到f数组，直接取最小值就ok了

下面是AC代码：有详细注释

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int N=1e6+100;

int head[N<<1],ct;

struct Edge
{
    int e;
    int to;
}edge[N<<1];

void add_edge(int u,int v)
{
    ct++;
    edge[ct].e=v;
    edge[ct].to=head[u];
    head[u]=ct;
}

int n;
int x,y;
int dep[N];//dep[u]表示节点u的深度 
int cnt[N];//cnt[u]表示节点u下的儿子个数,包含它本身 
int f[N];//f[u]表示以u为根节点,所有点深度和 


void dfs(int u,int fa)
{
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        if(v==fa)continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
} 

void dfs1(int u,int fa) 
{
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        if(v==fa)continue;
        dfs1(v,u);
        cnt[u]+=cnt[v];
    } 
}

void dfs2(int u,int fa)
{
    for(int i=head[u];i!=0;i=edge[i].to)
    {
        int v=edge[i].e;
        if(v==fa)continue;
        //遍历儿子节点,把每个儿子节点变成根,再计算f 
        f[v]=f[u]-cnt[v]+(n-cnt[v]); //核心,当v变成根节点,那么相当于v的所有孩子的深度都要减1,剩余节点的深度都要加1 
        dfs2(v,u); 
    } 
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1,0);//以1为根节点,求每个节点的深度 
//    for(int i=1;i<=n;i++)
//    {
//        printf("节点%d的深度为%d\n",i,dep[i]);
//    }

    //首先计算出以1为根节点,所有深度和 
    for(int i=1;i<=n;i++)
    {
        f[1]+=dep[i];
    }

    //printf("%d\n",f[1]); 

    for(int i=1;i<=n;i++)cnt[i]=1;//由于本身也算,所以初始为1 

    dfs1(1,0);//计算每个点的儿子数 

//    for(int i=1;i<=n;i++)
//    {
//        printf("节点%d的儿子数为%d\n",i,cnt[i]);
//    }

    dfs2(1,0);//从1出发,开始换根

    int minn=1e9;
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,f[i]);
    } 

    printf("%d\n",minn);
    return 0;
}