CF1187E

标签：sz int auto fa continue CF1187E include

 换根dp

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define IOS std::ios::sync_with_stdio(0)
using namespace std;
 #define int long long
const int  N=2e5+20;
 int n,sz[N],f[N],G[N];
 vector<int> g[2*N];
 
 void dfs1(int x,int fa){
 	sz[x]=1;
 	for(auto y:g[x]){
 		if(y==fa) continue; dfs1(y,x);
 		sz[x]+=sz[y];
 	}
 	int s=0;
 	for(auto y:g[x]){
 		if(y==fa) continue; 
 		s+=f[y];
 	}
 	f[x]=s+sz[x];
 }
 void dfs2(int x,int fa){
 	
 	for(auto y:g[x]){
 		if(y==fa) continue; G[y]=G[x]+n-2*sz[y];
 		dfs2(y,x);
 	}
 }
 signed main(){
 	int i,x,y;
    cin>>n;
    for(i=1;i<n;i++) 
    	cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
    
    dfs1(1,0); G[1]=f[1];
    dfs2(1,0);
    int ans=0; 
    for(i=1;i<=n;i++) ans=max(ans,G[i]);
    cout<< ans <<endl;
 }
 
 

 

标签：sz,int,auto,fa,continue,CF1187E,include
From： https://www.cnblogs.com/towboa/p/17277478.html