A. 和的期望
因为每一轮每一个数被选到的概率相同,所以期望的增量相同,所以答案就是 \(\frac {\sum a \times k}{n}\)。
B. 树上博弈
计算出每一个点的最优贡献,那么这个贡献是由子树中最优贡献最小的转移过来的。
维护一个子树最小值所在的节点即可。
C. 树的联结
计算一个树内的答案可以用换根DP。
计算两个棵树之间的答案,那么每一个节点一定选择距离它最远的节点作为连接边的其中一个端点,所以问题转换为了计算每个点的最远距离。
- 一个做法就是用树的直径做,答案一定是到直径两个端点的最大值。
- 一个做法是换根 DP 做,用一个 std::multiset 计算父节点传过来的答案即可,时间复杂度单 log。
D. 权值和 plus
待补
E. 寻找中位数 plus
待补
F. 十六度空间
待补