换根dp

 

题目链接

给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

vector<int> vec[N] ;
int dep[N] ;
int sz[N] ;
int sum[N] ;
void dfs1(int x, int f){
    dep[x] = dep[f] + 1 ;
    sz[x] = 1 ;
    for(auto e : vec[x]){
        if(e == f) continue ;
        dfs1(e,x) ;
        sz[x] += sz[e] ;
    }
}
void dfs2(int x,int f){//换根
    for(auto e : vec[x]){
        if(e == f) continue ;
        sum[e] = sum[x] - sz[e] + n - sz[e] ;
        dfs2(e,x) ;
    }
}
void solve(){
    cin >> n ;
    int t = n-1 ;
    int u, v ;
    while(t --){
        cin >> u >> v ;
        vec[u].push_back(v) ;
        vec[v].push_back(u) ;
    }
    dfs1(1,0) ;
    dfs2(1,0) ;
    int p = -1 ;
    ans = - INF ;
    for(int i = 1; i <= n ; ++ i){
        if(sum[i] > ans){
            ans = sum[i] ;
            p = i ;
        }
    }
    cout << p << endl ;
}