换根dp 80pts求助
查看原帖
换根dp 80pts求助
518124
yiyi049楼主2023/10/27 15:48
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 +5;
int cnt = 1,head[N];
struct edge{int to,nex;}e[2*N];
void add(int a,int b){cnt++;e[cnt].to=b;e[cnt].nex=head[a];head[a]=cnt;}
int n;
ll f[N],g[N],a[N];
void dfs1(int lst,int u){
	f[u] = 1,g[u] = 0;
	for(int i = head[u];i ;i = e[i].nex){
		if((i^1) != lst){
			int v = e[i].to;
			dfs1(i,v);
			f[u] += f[v];
			g[u] += g[v] + f[v];
		}
	}
}
void dfs2(int lst,int u){
//	if(lst){
//		a[u] = a[lst] + (-f[u]+n-f[u]);
//	}
	for(int i = head[u];i ;i = e[i].nex){
		int v = e[i].to;
		if(v != lst)
			a[v] = a[u] + (-f[v]+n-f[v]),
			dfs2(u,v);
	}
}
int main(){
	cin >> n;
	for(int i = 1;i < n; i++){
		int a, b;
		cin >> a >> b;
		add(a,b);
		add(b,a);
	}
	dfs1(-1,1);
	a[1] = g[1];
	dfs2(0,1);
	int ans=0,id = 0;
	for(int i = 1;i <= n; i++){
		if(a[i] > ans)id = i,ans = a[i];
	}
	cout << id;
	return 0;
} 
2023/10/27 15:48
加载中...