原题

E. Tree Pruning

解析

本题题意很简单, 思路也很好想到, 假设我们保留第 x 层的树叶, 那么对于深度大于 x 的所有节点都要被剪掉, 而深度小于 x 的节点, 如果没有子节点深度大于等于 x, 那么也要被删掉

在做这道题的时候, 有关于如何找到一个节点它的子节点能通到哪里, 是一个技巧, 我们可以在dfs回溯时确认

在知道这个之后, 这道题就非常简单了

代码

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 1000010;int n, m, k, q, ans, D;int cntdep[N], maxdep[N], cmd[N], e[N], ne[N], h[N], idx;void add(int u, int v)
{e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}void init()
{D = 0;for(int i = 0; i <= n; i ++ ){h[i] = -1;cntdep[i] = 0;cmd[i] = 0;}
}void dfs(int u, int f, int d)
{D = max(d, D);cntdep[d] ++;maxdep[u] = d;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (j != f){dfs(j, u, d + 1);maxdep[u] = max(maxdep[u], maxdep[j]);}}cmd[maxdep[u]] ++;
}void solve()
{cin >> n;init();for (int i = 1; i < n; i ++ ){int u, v;cin >> u >> v;add(u, v), add(v, u);}dfs(1, 0, 1);for (int i = 1; i <= D; i ++ ){cntdep[i] += cntdep[i - 1];cmd[i] += cmd[i - 1];}ans = n;if (n == 1){cout << 0 << "\n";return;}for (int i = 1; i <= D; i ++ ){int temp = n - cntdep[i] + cmd[i - 1];ans = min(ans, temp);}cout << ans << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}