70分求助 WA 先假设构建根节点为1的树,再在此基础不断变换根节点
  • 板块P1395 会议
  • 楼主小渣青999
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/8/19 16:42
  • 上次更新2023/11/6 19:55:42
查看原帖
70分求助 WA 先假设构建根节点为1的树,再在此基础不断变换根节点
170047
小渣青999楼主2020/8/19 16:42
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
struct node
{
	vector<int> v;
	int sum,len;//sum:包括根节点在内的节点和 len子树到根节点的距离和 
}t[100010];
int sub[100010];
vector<int> v[100010];

int vis[100010];
int ans=9999999,u;int n;
void dfs(int x,int step)
{
	int re=step;
	re-=t[x].sum;
	re+=(n-t[x].sum);
	if(re<ans) 
	{
		u=x;ans=re;
	}
	if(re==ans&&x<u) u=x;
	for(int i=0;i<t[x].v.size();i++)  dfs((t[x].v)[i],re);
}
void maket(int x)
{
	vis[x]=1;
	t[x].sum=1;t[x].len=0;
	for(int i=0;i<v[x].size();i++)
	{
		if(vis[v[x][i]]==0) 
		{
			t[x].v.push_back(v[x][i]);
			maket(v[x][i]);
			t[x].sum+=t[v[x][i]].sum; 
			t[x].len+=(t[v[x][i]].sum+t[v[x][i]].len);
		}
	}
	
}
int main ()
{
	
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	vis[1]=1;
	maket(1);
	
	for(int i=0;i<t[1].v.size();i++)  dfs((t[1].v)[i],t[1].len);
	 
	cout<<u<<" "<<ans;
	return 0;
}



2020/8/19 16:42
加载中...