前言

• 做总结时不要长篇大论，且内容要有意义（难点/错点）

---

题目

[BJOI2018] 求和

Solution

首先 $k$ 值很小，明显可以预处理，引入一个巧妙的定义（将节点和根连接/建立关系），设 $f_{u,k}$ 表示根到节点 $u$ 路径上所有节点深度的 $k$ 次方和，由此对于树上两个点，求完 LCA 后就可以很轻松的使用树上差分做到 $O(1)$ 查询。

---

遥远的国度

Solution

有三个操作：

• 1.换根
• 2.链修改
• 3.子树查询

本题的难点在于有个换根操作，考虑换根操作对查询操作的影响。首先自己画张图可以知道，只有当前的根 $u$ 和初始根 $rt$ 的路径上的节点在计算时才会改变，所以在查询 $x$ 的时候问题先转变为判断 $x$ 是否在 $u\to rt$ 的路径上，又出现一个套路了，用树剖求得 $lc{a}_{x,rt}$，再分类讨论判断：

• 1.若 $lc{a}_{x,u}\ne x$，$x$ 的子树没有发生变化，直接查询：
  • ① $x$ 和 $u$ 不在同一棵子树上；
  • ②在以 $rt$ 为根的树中 $x$ 在 $u$ 的子树中，很明显，这个贡献值也是不变的。
• 2.若 $lc{a}_{x,u}=x$，此时需要套用一个小技巧，需要用 dfs 序辅助解决，找出 $u\to rt$ 路径上 $lc{a}_{x,u}$ 的直系儿子 $v$，发现对答案没有贡献的是以 $v$ 为根的子树：
  • 在树剖中做 lca 时可以顺带记录，还要考虑一种特殊情况 $to{p}_x=to{p}_u$，那根据子树的重儿子序一定是连续的，直系儿子 $v$ 就是 $lc{a}_{x,u}$ 的重儿子了。
  • 最后通过 dfs 序，把贡献区域分为两段计算即可（画图感受）。

---

重拳出击

闲话

比较抽象，硬控我几小时，现在也只是勉强说服自己...

Solution

贪心：（木桶原理：答案是建立于最后一个解决的点）每次往距离最远的敌人走，当最远和次远一样时停止，等待即可。

小证明（乱证的）：设最远的距离为 $x$，次远的距离为 $y$。

如果先去走次远，则次数为 $\frac{x+1}{2}+\frac{y+1}{2}$（加 $1$ 是由于要向上取整），化简为 $\frac{x}{2}+\frac{y}{2}+1$;

如果先走最远，则次数为 $\frac{x-y+1}{2}+y$，化简为 $\frac{x}{2}+\frac{y}{2}+\frac{1}{2}$;

用做差法，明显走最远的更优。

解决方法：

• F1：树上换根+dfs序
• F2：找最远和次远+分类讨论（公式解决）