代码

A

.

B

因为 ，所以假设

完全在答案的精度范围内，可以忽略不计，也就是可以假设

直接解方程得

C

.

D

观察到 并不是很大，可以随便想想怎么做，往最短路方向去想，因为有 的限制，可以考虑下每次不休息一次就分一层图，最后一层只能强制往第一层走

就是分层图最短路

  • 每一层向下一层连边代表这个点不休息，代价为
  • 每一层点 向第一层点 连边代表这个点休息了一次，又可以重新计算未休息的点数，代价为

最后跑最短路就好了，需要特殊处理最后位置 的休息情况

E

看起来很像树的直径，因为要强制经过一个点，考虑换根 dp 解法的树的直径，设 分别表示从当前节点向子树的最长权值链和次长权值链，这样能够拼出来 一条跨过点 的链

还要考虑点 子树外的一些点对答案的贡献，设 表示 子树外，以 为起点的最长权值链，考虑这个怎么更新

套路的，我们用 来更新，如果 不是由 更新的，可以直接用 更新当前节点，否则只能用 更新，最后直接计算答案

F

跟 E 没啥关系吧

需要找到树上一条链 其中 为 的排列，并且

首先给 的每个值都设一个 unsigned long long 的随机值 ，然后求前缀异或

可以考虑异或哈希，以 的某个儿子 为开头的一条链 的异或值为 ，且 为 ，并且存在不以 为根的一条链的异或值为 ，那就可以计入答案

G

把 F 的做法搬过来，点分治一下，每次以分治中心为根做一遍