树学

题意：
给你一颗树，你选择一个节点当根，求所有点的深度和最少为多少？

思路：
树状dp+换根
一开始随便选一个点当根计算结果。
dp[i]表示以i为根的子树节点的深度和。
se[i]表示以i为根的子树的节点数目。
换根：
dp[v]=dp[u]+n-2*se[v];(v为u的子节点，根从u转向v时，以v为根的子树中的节点深度全减一，其余节点深度加一)

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll inf=1000000007;

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

vector<int> g[1000005];
ll dp[1000005], se[1000005];
int n;

void dfs(int v,int f,int d)
{
    dp[v]=d;
    se[v]=1;
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs(g[v][i],v,d+1);
            dp[v]+=dp[g[v][i]];
            se[v]+=se[g[v][i]];
        }
    }
}

void dfs1(int v,int f)
{
    if(f!=-1)
    {
        dp[v]=dp[f]+n-2*se[v];
    }
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs1(g[v][i],v);
        }
    }
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(), v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,-1,0);
    dfs1(1,-1);
    ll ans=inf*inf;
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}