首先找到树的直径，以其中点为根，这样做的好处是连通块一定是包含根节点的一个连通块，之后直接贪心求解，如果子节点能使答案减小选上即可。 关于树的直径，可以两次dfs找最远点，也可以用树形dp做。 时间复杂度\(O(n)\)。 根据关系图可以得到一个结论：父亲与儿子节点标号正好相差斐波那契数列中的某值，且这个值是小于儿子节点中最大的那个，下面有一个简单的证明。 在第\(k\)个月后一共有\(fib_k\)只兔子，其中\(fib_{k-1}\)只具有生育能力，将在第\((k+1)\)个月生下\(fib_{k-1}\)只兔子，其编号为\(fib_{k}+1,\cdots,fib_k+fib_{k-1}\)，其父亲编号正好是\(1,\cdots,fib_{k-1}\)，故得证。 由于\(fib_k > 2fib_{k-2}\)，即斐波那契数列是指数级膨胀的，因此树高是\(O(\log v)\)级别的，暴力向上跳找lca即可。 时间复杂度\(O(n\log^2 v)\)。 树上启发式合并(dsu on tree)的模板题。 考虑暴力做法，用dfs统计信息，当dfs到平行的下一课子树时，之前的信息就需要清掉，而当回到父亲节点统计其信息时，又需要将所有子树信息重新加回来，从而造成浪费。但根据这一逻辑，我们发现实际上dfs到的最后一个子树信号是不需要清空的，因此想办法把信息最多的子树（重儿子）最后一个dfs即可。 时间复杂度\(O(n\log n)\)。 首先注意到操作的顺序使不重要的，任意的操作顺序都能得到同样的结果，因此可以贪心地将\(t_i\)从大到小排序，最后肯定取它的一段前缀。 观察题意，发现要舍弃的是包括根节点（即节点1）在内的一个连通块内的权值，那么设\(f_{i,j}\)表示子树\(i\)中舍弃\(j\)个节点的最小权值和，若节点x有一个儿子y，那么有转移方程： 这是边dfs边做的，因此可以包含所有子树信息，同时注意需从后往前枚举，防止造成重算，跟01背包倒着枚举同理。 设\(\{T_i\}\)是\(\{t_i\}\)的前缀和，\(S\)为最初点权和，最终答案即为\(\max_{i=0}^n\{S+T_i-f_{1,i}\}\)。 时间复杂度\(O(n^2)\)。