E. Tree Pruning Codeforces Round 975 (Div. 2)
原题
解析
本题题意很简单, 思路也很好想到, 假设我们保留第 x 层的树叶, 那么对于深度大于 x 的所有节点都要被剪掉, 而深度小于 x 的节点, 如果没有子节点深度大于等于 x, 那么也要被删掉
在做这道题的时候, 有关于如何找到一个节点它的子节点能通到哪里, 是一个技巧, 我们可以在dfs回溯时确认
在知道这个之后, 这道题就非常简单了
代码
#include <bits/stdc++.h>
#define int long long
using 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();
}
}原文地址：https://blog.csdn.net/2301_81278039/article/details/142672113
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！