感受
原来换根操作是这样，虽然做的时候并不了解这个概念

思路
图片说明 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
struct edge{
    int v, nex;
}e[maxn * 2];
int n, head[maxn], cnt;
ll dp[maxn], num[maxn];///dp[i]表示以i为根的树的W      num[i]表示以i为根的树大小
void add_edge(int u, int v){
    cnt++;
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt;
}
void dfs1(int u, int f){
    int v;
    ll ans = 0; ll gg = 1;
    for(int i = head[u]; i > 0; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dfs1(v, u);
        gg += num[v];
        ans += dp[v] + num[v];
    }
    num[u] = gg;
    dp[u] = ans;
}
ll ans;
void dfs2(int u, int f){
    int v;
    for(int i = head[u]; i > 0; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dp[v] = dp[u] + n - 2 * num[v];
        ans = min(ans, dp[v]);
        dfs2(v, u);
    }
}
int main(){
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs1(1, 0);
    ans = dp[1];
    dfs2(1, 0);
    printf("%lld\n", ans);
    return 0;
}