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

116 阅读 0 评论 77 点赞

我是靠谱客的博主搞怪向日葵，这篇文章主要介绍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”（注意没有引号）

样例输入

复制代码

样例输出

复制代码

1
2
3
4
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#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;
}