CF1187E 7.20

__S08577__ · 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说似乎子树深度之和就是子树大小？