求助WA第5个点
  • 板块P1395 会议
  • 楼主lvyou
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/10/5 21:08
  • 上次更新2023/11/4 04:41:03
查看原帖
求助WA第5个点
248547
lvyou楼主2021/10/5 21:08
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+50;
int n,fa[N],size[N],g,u,v;
vector<int>G[N];
void dfs_size(int x)
{
	size[x]=1;
	if(G[x].size()==0)return;
	for(int i=0;i<G[x].size();i++)
	{
		if(G[x][i]!=fa[x])
		{
			fa[G[x][i]]=x;
			dfs_size(G[x][i]);
			size[x]+=size[G[x][i]];
		}
	}
	return;
}
int dfsg(int x)
{
//	cout<<"x:"<<x<<endl;
//	system("pause");
	for(int i=0;i<G[x].size();i++)
	{
		if(size[G[x][i]]>n/2&&G[x][i]!=fa[x])
		{
			return dfsg(G[x][i]);
		}
	}
	if(n-size[x]>n/2)return dfsg(fa[x]);
	return x;
}
int dfs(int x)
{
	int ans=0;
	size[x]=1;
	for(int i=0;i<G[x].size();i++)
	{
		if(G[x][i]!=fa[x])
		{
			fa[G[x][i]]=x;
			ans+=dfs(G[x][i])+size[G[x][i]];
			size[x]+=size[G[x][i]];
		}
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs_size(1);
	g=dfsg(1);
	if(size[g]==n/2&&n-size[fa[g]]+1==n/2)
	{
		g=min(fa[g],g);
	}
	if(n-size[g]+1==n/2)
	{
		if(g!=1&&G[g].size()==2)
		{
			g=min(g,G[g][0]^G[g][1]^fa[g]);
		}
	}
	fa[g]=g;
	cout<<g<<" "<<dfs(g);
	return 0;
}

求助大佬

2021/10/5 21:08
加载中...