记录编号	602289	评测结果	TTTTTTTTTT
题目名称	4165.一无所有	最终得分	0
用户昵称	惊世猴人	是否通过	未通过
代码语言	C++	运行时间	60.002 s
提交时间	2025-07-03 15:08:34	内存使用	44.46 MiB

#include<bits/stdc++.h>
using namespace std;
int n,t[100001];
int l,r;
int vis[100001],f[100001];
vector<int>v[100001],d;//防止是个n叉树 
int dis[100001];
inline void bfs(int start){
	queue<int>q;
	q.push(start);
	dis[start]=0;
	vis[start]=-start;
	while(!q.empty()){
		int e=q.front();
		q.pop();
		for(int x=0;x<v[e].size();x++){
			int i=v[e][x];
			if(vis[i]!=-start){
				dis[i]=dis[e]+1;
				q.push(i);
				vis[i]=-start;
			}
		}
	}
//	for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
	putchar('\n');
}
int dfs(int e,int bj){
//	cout<<e<<' ';
	vis[e]=bj;
	int ans=INT_MAX,a=0;
	for(int x=0;x<d.size();x++){
		int i=d[x];
		if(dis[i]<dis[e])continue;
		ans=min(dis[i],ans);
	}
	if(ans<=2*dis[e]||ans==INT_MAX)return 1;
	for(int x=0;x<v[e].size();x++){
		int i=v[e][x];
		int c=dfs(i,bj);
		a+=c;
//		printf("%d has called %d for help\n",e,c);
	}
	return a;
} 
int main(){//抽象化题意得对于树上任意一点，求到树叶的方案数 ，若已经在树叶上为1
	freopen("nothing.in","r",stdin);//起点为s当前点为u最近叶子为v,当路径dis(s,u)>=dis(u,v)只需要堵一个 
	freopen("nothing.out","w",stdout);//否则对u的儿子进行同样操作 
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>l>>r;
		t[l]++;
		t[r]++;
		v[l].push_back(r);
		v[r].push_back(l);
	}
	for(int i=1;i<=n;i++)if(t[i]==1)d.push_back(i);
	for(int i=1;i<=n;i++){
		if(t[i]==1)puts("1");//叶子 
		else bfs(i),cout<<dfs(i,i)<<"\n"; 
	} 
	fclose(stdin);
	fclose(stdout);
	return 0;
}