题解 |gk的树

gk的树

https://ac.nowcoder.com/acm/contest/30825/F

https://ac.nowcoder.com/acm/contest/30825/F 有个问题 这个问题听困扰我的 ,我真的不知道如何解决 就这个减枝怎么减的 就是这个图怎么画呢 怎么dfs 减枝的呢 看了好多大神的代码 也是 不懂 这个dfs 有没有大哥帮忙看一下的啊大哥们+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

alt

这个是 那个树图

alt

凉心哥哥的小宝藏 文章被收录于专栏

c++

全部评论
另一种写法 但是意思相同 希望能给你提供帮助 从叶子节点开始处理 若叶子节点度数大于k 就删边 模拟一下倒推回根节点 ``` void dfs(int u, int fa) { cnt[u] = (fa > 0); for(auto v : e[u]) { if(v == fa) continue; dfs(v, u); cnt[u] ++; } if(cnt[u] > k) res += cnt[u] - k, cnt[fa] --; //因为下面的树怎么砍都无法对上面做贡献了 所以度数只需要对fa -1 } ```
1 回复 分享
发布于 2022-04-05 16:18
我的理解是一个从上往下砍树的过程。d -= dfs(x) 相当于砍掉了一棵子树。后面就是判断当前树要不要被砍掉。 emmm我也不是很确这样理解对不对,毕竟我也写不出来orz ```CC int dfs (int u) { int len = v[u].size(); //初始度数 for (auto i : v[u]) { //遍历所连边 if (vis[i]) continue; vis[i] = true; len -= dfs (i); //需要剪枝就-1,没被剪过就咔嚓剪掉 } if (len <= k) return 0; //不需要操作 ans += len - k; //多出来了多少边 return 1; } ```
点赞 回复 分享
发布于 2022-04-04 12:34

相关推荐

孙艹肘:校招不给三方直接让实习我都去了,,主打一个在学校呆着也是闲着,不如出来实习一下
点赞 评论 收藏
分享
顺利毕业的鸽子:这个不一定,找hr跟进一下
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务