P3260 修剪树叶

按照题意，每轮删去当前所有的叶子节点。

用 $cnt$ 表示当前是第几次操作。

使用拓扑排序优化搜索，用一个数组 $d_i$ 记录 $i$ 的度数，每轮删除叶子节点时，将与其相连的节点的度数 $-1$ ，如果发现该节点度数为 $1$ ，就说明它是叶子节点，把它加进队列中。

因为要记录现在是第几次操作，所以要用两个队列分开存放叶子节点，一个是当前操作的编号，另一个存下一轮操作的节点，下标用 $now$ 和 $nxt$ 表示，每轮结束后，交换 $now$ 和 $nxt$ ，类似于 $dp$ 的滚动数组。

代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,u,v,d[100001],ans[100001],cnt,now,nxt=1,sum;
vector<int> g[100001];
queue<int> q[2];
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		d[u]++;
		d[v]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)if(d[i]==1)q[now].push(i);
	while(sum!=n){
		cnt++;
		while(!q[now].empty()){
			sum++;
			u=q[now].front();
			q[now].pop();
			ans[u]=cnt;
			int siz=g[u].size();
			for(int i=0;i<siz;i++){
				v=g[u][i];
				d[v]--;
				if(d[v]==1)q[nxt].push(v);
			}
		}
		swap(now,nxt);
	}
	for(int i=1;i<=n;i++)printf("%d ",ans[i]);
}