题目描述：

  牛妹有一张连通图，由 个点和 条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度 ​ 为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如为根，的；路径为 时， 的父节点是 ，并且满足对任意非根节点，，整棵树的价值 ，即所有点的深度和。
求出 。
数据范围：

解法一：

  以树的重心为根，因为树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。
如果有多个重心也没关系，只需判断一个重心即可。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+6;
int balance,n,cnt;
ll res;
int sz[N],root[N];
vector<int>pic[N];
void dfs1(int v,int p)
{
    sz[v]=0;
    int re=0;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
        {
            dfs1(u,v);
            sz[v]+=(sz[u]+1);
            re=max(sz[u],re);
        }
    }
    re=max(n-sz[v]-1,re);
    if(re<balance)
    {
        cnt=0;
        root[++cnt]=v;
        balance=re;
    }
    else if(re==balance)
        root[++cnt]=v;
}
void dfs2(int v,int p,int d)
{
    res+=d;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
            dfs2(u,v,d+1);
    }
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].pb(v);
        pic[v].pb(u);
    }
    balance=N;
    dfs1(1,0);
    dfs2(root[1],0,0);
    ll ans=res;
    /*for(int i=2;i<=cnt;i++)
    {
        res=0;
        dfs2(root[i],0,0);
        ans=min(res,ans);
    }*/
    printf("%lld\n",ans);
    return 0;
}

解法二：

  对于同一条边的两个端点 和 ，一开始以 树的根，当把根转移到点 时，所有点的深度和的改变量为。可以 进行转移，枚举每个点求出最小值即可。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e6+5;
vector<int>pic[N];
ll ans;
int sz[N];
void dfs(int v,int p,int d)
{
    sz[v]=1;
    ans+=d;
    for(int i=0;i<pic[v].size();i++)
    {
        int u=pic[v][i];
        if(u!=p)
        {
            dfs(u,v,d+1);
            sz[v]+=sz[u];
        }
    }
}
int main()
{
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        pic[u].pb(v);
        pic[v].pb(u);
    }
    ans=0;
    dfs(1,0,0);
    for(int i=2;i<=n;i++)
        ans=min(ans,ans+(n-sz[i])-sz[i]);
    printf("%lld\n",ans);
    return 0;
}