做题记录整理图论2 P6591. [YsOI2020] 植树（2022/10/3）

P6591. [YsOI2020] 植树

是一道相对比较简单的题，但是为什么还要对它进行总结呢？

因为里面有一种先固定一个根来算子树大小，之后再进行计算的想法我之前似乎没有做过类似的题

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;

struct node{
	int nex;
	int to;
	
}a[10000005];
int n,vis[10000005],cnt,hd[10000005],dep[10000005];
void add(int x,int y)
{
	a[++cnt].to=y;
	a[cnt].nex=hd[x];
	hd[x]=cnt;
}
int dfs(int x,int fa)
{
	vis[x]=1;
	int ji=0;
	for(int i=hd[x];i;i=a[i].nex)
	{
		int v=a[i].to;
		if(v==fa) continue;
		dep[x]+=dfs(v,x);
		if(!ji) ji=dep[v];
		if(ji!=dep[v]) vis[x]=0;
	}
	dep[x]++;
	if(x!=1&&ji&&ji!=n-dep[x]) vis[x]=0;
	return dep[x];
}
int main()
{
	cin>>n;
	int x,y;
	for1(i,1,n-1)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	
	for1(i,1,n)
		if(vis[i])
			printf("%d ",i);
	return 0;
}