首页 > Bob in Wonderland
开通博客写题解
头像 __故人__
发表于 2020-10-03 19:54:48
分析 给你一棵树，求至少要几次操作，变化为一条链。我们知道无论变化多少次总度数一定不变 。而一条链的度数分布为 根据鸽巢原理，只要对于 的节点操作 次就可以了。总的复杂度为 。 代码 #include<bits/stdc++.h> const int N = 3e5 + 100 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 阿哲不是吧
发表于 2020-10-01 16:49:04
Bob in Wonderland 题意： 一棵树，问最少移动多少次边可以使其变成一个链？移动是指：从原位置拆下并连到新位置，这样算一次 题解： 错误思路 我一开始在想既然求最少移动次数，那我们就尽可能在原本的就存在的链的基础上进行修改，也就是先找树中最长的链（即树的直径），然后看这条链上有多少子链 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”