2020.2.7 C组模拟赛第四题【树的重心】

109 阅读 0 评论 72 点赞

我是靠谱客的博主搞怪向日葵，最近开发中收集的这篇文章主要介绍2020.2.7 C组模拟赛第四题【树的重心】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

“尼伯龙根是一棵由n-1条高架路连起n 个地区的树，每一次Load，你都会重生在某一个地区。如果重生点是整个尼伯龙根的重心，也就是这个树的重心，那么你就能在最短时间内带诺诺逃脱啦。”
“对了，再给你一点方便咯，你可以选一条高架桥断掉，再连接另外两个地方，每次Load只能用一次技能，而又必须使整个它仍构成树形结构。你的Save点在这里，Load自然会恢复原始的尼伯龙根咯。”

输入

第一行两个整数n,m，n意义如题，m表示路明非Load了m次。
接下来n-1行，每行两个整数x,y表示节点x,y之间存在一条边。
接下来m行，每行一个整数p,表示这次Load的重生地区。

输出

对于每一个询问，输出一行
如果可以则输出”YES”，否则输出”NO”（注意没有引号）

样例输入

样例输出

YES
NO
NO

分析：

找到树的重心，询问x个点，去掉任意一条边，又连上任意两点，求出它能否成为树的重心
就可以找出重心的最大和次大子树，如果i在最大子树上，就将次大子树连上x，不然就将最大子树连上x，再判断这个点是否符合重心。

CODE：

#include<cmath>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
int jl[400000],s[400000],g[400000],a[400000],f[400000],x[400000],y[400000];
int n,m,dian,i,p,ji,maxx,max2,jis,ans;
int h[400000][100];
bool bz[400000],zhi[400000],bo;
void dg(int k)
{
	int i,p;
	if(k==12) k=k;
	for(i=1;i<=g[k];i++)
	{
		p=h[k][i];
		if(bz[p]==false)
		{
			bz[p]=true;
			dg(p);
			f[k]=f[k]+f[p];
		}
	}
	f[k]++;
} 
void dg2(int k)
{
	int i,p,t,s;
	s=n-f[k];
	if(bo)
	return;
	s--;
	for(i=1;i<=g[k];i++)
	{
		p=h[k][i];
		if(bz[p])
		continue;
		if(s<f[p])
		s=f[p];
	}
	if(s<=n/2)
	{
		bo=true;
		dian=k;
		return;
	}else
	{
		for(i=1;i<=g[k];i++)
		{
			if(bz[h[k][i]])
			continue;
			bz[h[k][i]]=true;
			dg2(h[k][i]);
			if(bo)
			return;
		}
	}
}
void jilu(int k)
{
	int i,p;
	zhi[k]=true;
	for(i=1;i<=g[k];i++)
	{
		p=h[k][i];
		if(bz[p]==false)
		{
			bz[p]=true;
			jilu(p);
		}
	}
}
int main(){
	freopen("h3.in","r",stdin);
	freopen("h3.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		g[x[i]]++;
		h[x[i]][g[x[i]]]=y[i];
		g[y[i]]++;
		h[y[i]][g[y[i]]]=x[i];
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	memset(bz,false,sizeof(bz));
	memset(f,0,sizeof(f));
	bz[x[1]]=true;
	dg(x[1]);
	memset(bz,false,sizeof(bz));
	bo=false;
	bz[x[i]]=true;
	dg2(x[1]);
	memset(f,0,sizeof(f));
	memset(bz,false,sizeof(bz));
	bz[dian]=true;
	dg(dian);
	for(i=1;i<=g[dian];i++)
	{
		p=h[dian][i];
		if(maxx<f[p])
		{
			maxx=f[p];
			ji=p;
			jis=i;
		}
	}
	memset(bz,false,sizeof(bz));
	memset(zhi,false,sizeof(zhi));
	bz[dian]=true;
	bz[ji]=true;
	ans=1;
	jilu(ji);
	for(i=1;i<=g[dian];i++)
		if(i!=jis)
		{
			p=h[dian][i];
			if(max2<f[p])
			max2=f[p];
		}
	for(i=1;i<=m;i++)
	{
		if(a[i]==dian)
		{
			cout<<"YES"<<endl;
			continue;
		}if(zhi[a[i]])
		{
			if(n-f[a[i]]-max2<=n/2)
			cout<<"YES"<<endl;
			else
			cout<<"NO"<<endl;
		}
		else{
			if(n-f[a[i]]-maxx<=n/2)
			cout<<"YES"<<endl;
			else
			cout<<"NO"<<endl;
		}
	}
	
return 0;
}