首页 > 其他分享 >P3478

P3478

时间:2024-10-23 19:02:55浏览次数:2  
标签:std 1000010 struct nxt 题解 P3478

题解

#include<bits/stdc++.h>
using namespace std;
struct edge {
	int to,nxt;
} e[1000010<<1];
int n,cnt,id;
int head[1000010];
long long ans;
long long f[1000010],dep[1000010],size[1000010];
inline void add(int u,int v){
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void dfs1(int x,int fa){
	size[x]=1;
	dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa)continue;
		dfs1(y,x);
		size[x]+=size[y];
	}
}
void dfs2(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa)continue;
		f[y]=f[x]+n-2*size[y];
		dfs2(y,x);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++)f[1]+=dep[i];
	dfs2(1,0);
	for(int i=1;i<=n;i++)if(ans<f[i])ans=f[i],id=i;
	printf("%d",id);
	return 0;
}

标签:std,1000010,struct,nxt,题解,P3478
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18498074

相关文章

  • P3478 STA-Station/换根 $dp$ 板子
    P3478[POI2008]STA-Stationlink给定一个\(n\)个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大。一个结点的深度之定义为该节点到根的简单路径上边的数量。对于全部的测试点,保证\(1\leqn\leq10^6\),\(1\lequ,v\leqn\),给出的是一棵树。思路:树......
  • P3478 [POI2008] STA-Station
    题目链接:既然让求深度之和,那么我就定义以\(i\)为根时深度之和为\(f_i\),现在就是思考状态转移的问题。如果以某种手段得到了\(f_1\),那么接下来的转移就好说了。设\(u\)为当前节点,\(j\)是当前节点的子节点。\(s_i\)表示以\(i\)为根的子树中的节点数量,则\(s_u=1+\sum{s......
  • P3478 [POI2008] STA-Station
    原题链接WARNING!!!使用map代替数组不再可靠,因为map的插入查找修改复杂度均为\(O(logn)\),即使unorder_map也不行!!!题解我们发现,当一个节点的深度之和已知时(这里认为是根节点),其相邻节点的深度之和也可通过某种方程转移而得,有人称这种方法为换根DP具体的,将树拆开成图(求深度之和......
  • 洛谷-P3478 STA-Station
    STA-Station换根dp模板去到相邻的点可以根据去到的点的子树有多少个结点,来调整当前的值#include<iostream>#include<cstdio>#include<algorithm>#include<vecto......