前言

• 显而易见，这是个挂分+玄学错误的比赛题目。

---

题目

Two Chess Pieces

Solution

树上 dp 题，怎么说呢，正难反则易，两个棋子走完整个树再回到根的步数是 $4\times (n-1)$；

再考虑固定一个棋子，另一个棋子向下走的情况，前提条件是固定的棋子在子树中没有任务，且另一个棋子的任务的最大深度减去固定棋子的任务的深度要小于 $d$，减去两点贡献即可。

---

ρars/ey

重点

• 树上背包的时间复杂度优化 $O(n^2)$。

先假设要取总大小为 $m$ 的物品，状态转移为：

$f_{u,j}=max(f_{u,j-k},f_{v,k})$；

优化上下界：

• 1.当前背包大小大于 $s{z}_u+s{z}_v$ 是无用的转移，故上界取 $min(m,s{z}_u+s{z}_v)$；

• 2.当前已知的状态大小为 $s{z}_u$，所以 $j-k>s{z}_u$ 的都是无用转移，即 $k<j-s{z}_u$ 都是没用的，所以有用状态满足 $k\ge j-s{z}_u$，在程序中 $k$ 初始值取 $max(0,j-s{z}_u)$，优化下界；

• 3.当下儿子已知的状态数大小为 $s{z}_v$，所以由儿子转移过来的状态应该满足 $k\le s{z}_v$，优化了上界。

时间复杂度证明（简要）：

对于一棵树内的任意两个点都进行了转移，那么有 $n$ 个节点，点对的个数就为 $\frac{n\times (n-1)}{2}$，故为 $O(n^2)$。