本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-20 17:05:41

鸣谢

@Firacode

题意

https://codeforces.com/problemset/problem/1187/E

思路

这道题显然发现可以用树形dp。

首先，一般的树形DP都是自下而上进行的，不妨我们也先自下而上DP。设 $f_i$ 为以 $i$ 为根把 $i$ 染成黑色答案。根据题意，我们发现 你获得的分数等于包含该顶点的、仅由白色顶点组成的连通块的大小，所以 $f_u+=size_u$，然后接着遍历下面的子树，所以 $f_u=size_u+ \sum_{v ∈ son \ u} f_v$。但是发现，这种时间复杂度为 $O(N^2)$，直接爆炸。

但是，我们不难想到换根DP。换根时，除了换根的两个点，其他子树的 $size$ 不变。 比如，原根为 $u$，换的根是 $v$，那么 $size_u$ 减少了 $size_v$，$size_v$ 增加了 $n-size_v$。设 $g_i$ 为以 $i$ 为根的答案，根据上面的推断，$g_v=g_u+n-2*size_v$。

两遍dfs求出答案。

#include<iostream>
using namespace std;
const int N=2e5+10;\/\/注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;
int n;
int f[N],g[N],sz[N];
vector<int> ve[N];
void dfs1(int u,int fa){
    sz[u]=1;
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        if(v==fa) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        f[u]+=f[v];
    }
    f[u]+=sz[u];
}

void dfs2(int u,int fa){
    for(int i=0;i<ve[u].size();i++){
        int v=ve[u][i];
        if(v==fa) continue;
        g[v]=g[u]+n-2*sz[v];
        dfs2(v,u);
    }
}

\/*
 *\/
signed main(){
    
\/\/   freopen("a.in","r",stdin);
\/\/   freopen("a.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    dfs1(1,0);
    g[1]=f[1];
    dfs2(1,0);
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,g[i]);
    }
    cout<<maxx;
    return 0;
}

zph说似乎子树深度之和就是子树大小？