分析

给你一棵树，求至少要几次操作，变化为一条链。我们知道无论变化多少次总度数一定不变 $\sum du_i=2\times n-2$ 。而一条链的度数分布为 $1,2...2,2,1$ 根据鸽巢原理，只要对于 $du_i>2$ 的节点操作 $du_i-2$ 次就可以了。总的复杂度为 $O(n)$ 。

代码

#include<bits/stdc++.h>
const int N = 3e5 + 1000;
int du[N],n,ans;
int main() {
    scanf("%d",&n);for(int i = 1,a,b;i < n;i++) scanf("%d%d",&a,&b),du[a]++,du[b]++;
    for(int i = 1;i <= n;i++) ans += du[i] > 2?du[i] - 2:0;printf("%d\n",ans);
}