codeforces-1593E -Gardener and Tree

题目大意：

有一颗无向边连接的树，每次操作剪掉所有的叶子节点。问k次操作后还剩下多少个节点。

思路和代码：

​ 说实话这个题目一拿到我就想把每个点的深度算出来，毕竟o(n)。但是越想越不对，这棵树妹有根啊！！没有根的树怎么做深搜找深度呢？搜了一篇题解之后我悟了=>传送门

​ 下面记录一下思考过程：

​ 每一次删除的都是叶子节点，所以我们应该记录的是每一个节点到叶子节点的最大距离。我一般做树的题目用的都是dfs，这里要用bfs从叶子节点一层一层往中心走进去，有点像剥卷心菜啊。

cin >> n >> m ;//初始化
for(int i = 1 ; i <= n ; i ++ ) dep[i] = 0 ;
for(int i = 1 ; i <= n ; i ++ ) eg[i].clear() ;
for(int i = 1 ; i < n ; i ++ ){//双向边
	ll u , v ; cin >> u >> v ;
	eg[u].push_back(v) ;
	eg[v].push_back(u) ;
}
for(int i = 1 ; i <= n ; i ++ ) num[i] = eg[i].size() ;

然后开始从叶子到里面，由外而内的bfs：

queue<ll> q ;
	
for(int i = 1 ; i <= n ; i ++ )
    if(num[i] == 1){
        q.push(i) ;//叶子节点入队
        dep[i] = num[i] -- ;//该点连接的边数减少
    }

while(q.size()){
    ll now = q.front() ;
    q.pop() ;
    for(auto i : eg[now]){
        if(!num[i]) continue ;
        dep[i] = dep[now] + 1 ;//更新该点到叶子的最远
        if( -- num[i] == 1) q.push(i) , num[i] -- ;
    	//点用过后要减去一条边，若只有一条边了就是叶子，就要入队并且把自己从num中清零
    }
}

最后做答案，只要这个点的dep大于m就是剩下来的。

ll ans = 0 ;
for(int i = 1 ; i <= n ; i ++ )
if(dep[i] > m) ans ++ ;

cout << ans << "\n" ;

写在后面

这个题目的bfs处理很巧妙，记录一下。