树的重心,8个点爆零,奇了怪了
  • 板块P1395 会议
  • 楼主H_F_lenz
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/7/17 10:14
  • 上次更新2023/11/6 22:59:03
查看原帖
树的重心,8个点爆零,奇了怪了
271023
H_F_lenz楼主2020/7/17 10:14
#include<bits/stdc++.h>
using namespace std;
int m,num=0,flag=0,siize[100010]={0},top=0,hp[100010]={0},tc=0,v[100010]={0},st[100010]={0},n,p=0,dfn[100010]={0},low[100010]={0},ans=0x3f,a[200010]={0},w[500002]={0},head[500002]={0},Next[1000004]={0},ver[1000004],tot=0,d[500001]={0},t;
void add(int a,int b)
{
	ver[++tot]=b;
	Next[tot]=head[a];
	head[a]=tot;
	hp[tot]=a;
}
void dfs(int x)
{
	v[x]=1;siize[x]=1;
	int max_part=0;
	for(int i=head[x];i;i=Next[i])
	{
		int y=ver[i];
		if(v[y])
		continue ;
		dfs(y);
		siize[x]+=siize[y];
		max_part=max(max_part,siize[y]);
	}
	max_part=max(max_part,n-siize[x]);
	if(max_part<ans)
	{
		ans=max_part;
	    t=x;
    }  
    if(max_part==ans)
	{
		ans=max_part;
	    t=min(x,t);
    }  
}
void bfs()
{
	memset(v,0,sizeof(v));
	queue <int> q;
	q.push(t);
	d[t]=0;
	v[t]=1;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=Next[i])
		{
			int y=ver[i];
			if(v[y]==0)
			{
				v[y]=1;
				d[y]=d[x]+1;
				num+=d[y];
				q.push(y);
			}
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1);
	memset(v,0,sizeof(v));
	bfs();
	cout<<t<<" "<<num;
}
2020/7/17 10:14
加载中...