凉心丫 level
获赞
42
粉丝
5
关注
5
看过 TA
20
黑龙江工程学院
2025
Web前端
IP属地:北京
Dealth_Knight
私信
关注
2022-04-03 22:36
已编辑
黑龙江工程学院 Web前端
https://ac.nowcoder.com/acm/contest/30825/F 有个问题 这个问题听困扰我的 ,我真的不知道如何解决 就这个减枝怎么减的 就是这个图怎么画呢 怎么dfs 减枝的呢 看了好多大神的代码 也是 不懂 这个dfs 有没有大哥帮忙看一下的啊大哥们+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++  这个是 那个树图
DM_11:另一种写法 但是意思相同 希望能给你提供帮助 从叶子节点开始处理 若叶子节点度数大于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 } ```
凉心哥哥的小宝藏
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客网在线编程
牛客网题解
牛客企业服务