C. Tree Pruning【Codeforces Round 975 (Div. 1)】
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;
}
原文地址：https://blog.csdn.net/2303_79310336/article/details/142683353
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！