C. Tree Pruning
(永远不知道为什么TLE直到把初始化的memset换成for循环
题意很简单，就是找到一个深度，使得删除最少的节点且所有的叶子节点都为这个深度。
从小到大遍历可能的深度i，容易知道所有 深度大于i的节点 和所有 子树最大深度小于i的节点 都应该被删去。
用dfs计算每个节点的子树的最大深度和每个子树最大深度的节点个数，以及每个深度的
节点数，然后就可以递推地计算出每个深度i应该保留的节点数cur，最后保存答案n-cur的最小值。
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;struct node {int fa; //父节点int dep;vector<int> l; //临接
} d[500005]; //存储节点int cntd[500005]; //每个深度有多少个节点
int ldp = 0; //最大深度int mxdp[500005]; //每个节点的子树的最大深度
int mdpn[500005]; //每个 子树最大深度 的节点计数void dfs(int x) {int fa = d[x].fa;if (fa != -1)d[x].dep = d[fa].dep + 1;ldp = max(ldp, d[x].dep); //当前深度的节点计数mxdp[x] = d[x].dep; //初始化当前节点的子树最大深度为自身深度for (int e : d[x].l) {if (e == d[x].fa) continue;d[e].fa = x;dfs(e);mxdp[x] = max(mxdp[x], mxdp[e]); // 更新子树最大深度}cntd[d[x].dep]++;mdpn[mxdp[x]]++; //增加当前子树最大深度的节点计数
}void solve() {ldp = 0;d[1].fa = -1;d[1].dep = 1;int n;cin >> n;for (int i = 1; i <= n; i++) {d[i].l.clear();cntd[i]=mxdp[i]=mdpn[i]=0;}for (int i = 0; i < n - 1; i++) {int u, v;cin >> u >> v;d[u].l.pb(v);d[v].l.pb(u);}dfs(1);int ans = INF, cur = 0;for (int i = 1; i <= ldp; i++) {cur += cntd[i]; // 累加当前深度的节点数ans = min(ans, n - cur); // 更新最小操作数cur -= mdpn[i]; // 减去当前深度的最大深度节点数}cout << ans << endl;
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}
)
