题意

• 一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和
• 求选择哪个点为根时可以使深度和最小

思路

• 让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和
• 但是让每一个点跑一遍复杂度会爆炸
• 能不能只跑一遍？如果只跑一遍，根变换怎么办
• 对于一个选定根的树，如果把根的一个子节点提升为根，则除了这个子节点所在子树以外的结点都下降了一层，子节点所在子树上升了一层
• 则总和的变换就可以推出
• 任选一个点为根，维护每个点深度和子树，然后再跑一遍dfs表示换根，跑出每一个点为根的时候的sum
• 最后遍历每一个sum维护出答案即可

代码

#include<bits/stdc++.h>
using namespace std;
/**
 * 对已知根情况下求总深度直接dfs就可以
 * 如果把原有根a和子树根b互换，b上的所有点深度-1，其它点深度+1
 * sum[b]=sum[a]-cnt[b]+(n-cnt[b])
 * 一遍dfs求任意一个根，一个dfs换根即可
 */
vector<int> G[1010101];
int dep[1010101],cnt[1010101];
long long f[1010101];
int n;
void dfs1(int x,int fa){
    cnt[x]=1;
    for(auto i:G[x]){
        if(i==fa) continue;
        dep[i]=dep[x]+1;
        dfs1(i,x);
        cnt[x]+=cnt[i];
    }
}

void dfs2(int x,int fa){
    for(auto i:G[x]){
        if(i==fa) continue;
        f[i]=f[x]-cnt[i]+(n-cnt[i]);
        dfs2(i,x);
    }
}
int main(){
    cin >> n;
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++){
        f[1]+=dep[i];
    }
    dfs2(1,0);
    long long ans=f[1];
    for(int i=2;i<=n;i++){
        ans=min(ans,f[i]);
    }
    cout << ans << endl;
    return 0;
}