在树上进行操作的记忆化搜索，通过DFS加灵活换根的方式进行。
首先先走一遍DFS，得到每个节点下的深度和，节点的个数和（包括节点自身）。
然后让1成为根，那么再进行DFS下去的每一个节点都可以有一个动态规划递推式来快速计算得到加入某个节点为根的时候的深度和。
递推式为：dp[x] = dp[fa] - num[x] + n - num[x]。
其实某个节点作为根的深度和就等于上一个节点作为根的深度和加上因为根的改变而距离增大的节点数目以及减去因为根改变而距离减少而节点数目。 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
int n;
int ans = INT_MAX;
int dp[maxn];
int dep[maxn];
int num[maxn];
vector<int> son[maxn];
pair<int, int> DFS(int x, int fa, int depth)
{
    int len = son[x].size();
    int tol_dep=depth, tol_cnt=1;
    for (int i=0;i<len;i++)
    {
        if (son[x][i]==fa) continue;
        pair<int, int> pr = DFS(son[x][i], x, depth+1);
        tol_dep += pr.first;
        tol_cnt += pr.second;
    }
//    cout<<"x="<<x<<endl;
//    cout<<"tol_dep="<<tol_dep<<" tol_cnt="<<tol_cnt<<endl;
    dep[x] = tol_dep;num[x] = tol_cnt;
    return make_pair(tol_dep, tol_cnt);
}

void triangle(int x, int fa)
{
    int len = son[x].size();
    if (x==1)
        dp[x] = dep[x];
    else
        dp[x] = (dp[fa]) - num[x] + n - num[x];
//     cout<<dp[x]<<endl;
    ans = min(ans, dp[x]);
    for (int i=0;i<len;i++)
    {
        int next = son[x][i];
        if (next==fa) continue;
        triangle(next, x);
    }
}

signed main()
{
    cin>>n;
    int x, y;
    for (int i=1;i<n;i++)
    {
        cin>>x>>y;
        son[x].push_back(y);
        son[y].push_back(x);
    }
    //先走一遍DFS去填充以1为根的每个节点下的深度以及节点个数。
    DFS(1, 0, 0);
    //走一遍记忆化搜索，然后求出最小的答案。
    triangle(1, 0);
    cout<<ans;
    return 0;
}