标签：cnt int 合并 ans ABC303E define

[ABC303E] A Gift From the Stars

每次合并都是合并入度为 \(1\) 的点，所以合并的一定不是中心，且被合并后入度是 \(2\)。因此如果某个节点的入度 \(\ge 3\)，那么这个节点一定是中心。对于剩余的点，因为保证有解，直接当作大小为 \(2\) 的星处理。（注意大小为 \(2\) 的星共 \(3\) 个点）。

#include<cstdio>
#include<algorithm>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=200010;
int n,d[N],ans[N],cnt;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	#endif
	// Insert Code Here
	scanf("%d",&n);
	E(i, n-1){
		int a,b;
		scanf("%d%d",&a,&b);
		++d[a],++d[b];
	}
	int s=n;
	E(i, n)
		if(d[i]>=3)ans[++cnt]=d[i],s-=d[i]+1;
	E(i, s/3)printf("%d ",2);
	sort(ans+1,ans+1+cnt);
	E(i, cnt)printf("%d ",ans[i]);
	return 0;
}

标签：cnt,int,合并,ans,ABC303E,define
From： https://www.cnblogs.com/wscqwq/p/17453403.html