1187E.Tree Painting_牛客博客

$Description$
给定一颗树,求以任意结点为根,所有子树大小的和的最大值.

$Solution$
树形 $dp$ ,换根.先以任意结点为根,处理出 $dp$ 数组, $dp[i]$ 表示子树 $i$ 中所有子树大小的总和.然后在进行一边遍历,进行换根操作,推出转移方程: $dp[v]=dp[u]+n-2 \cdot sz[v]$

$Code$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
ll ans=0;
int n;
vector<int>g[N];
ll dp[N]={0},sz[N]={0};
void dfs(int u,int fa){
    sz[u]=1;
    for(auto v:g[u]){
        if(v^fa){
            dfs(v,u);
            sz[u]+=sz[v];
            dp[u]+=dp[v];
        }
    }
    dp[u]+=sz[u];
}
void bfs(int u,int fa){
    ans=max(ans,dp[u]);
    for(auto v:g[u]){
        if(v^fa){
            dp[v]=dp[u]+n-2ll*sz[v];
            bfs(v,u);
        }
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    bfs(1,0);
    o(ans);
}