有一棵 \(n\) 个节点的树，编号为 \(i\) 的点权值为 \(h_i\)。
你有 \(k\) 个棋子，第 \(i\) 个棋子初始在编号为 \(s_i\) 的点上。你需要进行若干次移动，每次移动可以将一个棋子移到相邻的点上。特别的，多个棋子可以在同一个点上。你需要将第 \(i\) 个棋子移动到编号为 \(t_i\) 的点上。
设第 \(i\) 个棋子在编号为 \(p_i\) 的点上，我们定义当前状态的势能为 \(\sum\limits_{i=1}^{k} h_{p_i}\)。你需要最小化移动过程中势能的最大值。
\(1 \leq n,k \leq 2000\)，\(1 \leq h_i \leq 10^9\)。
草，学习了一下午发现理解错了。
我们不妨先定义一种严格的偏序关系：若 \(p_u < p_v\) 或 \(p_u = p_v\) 且 \(u < v\)，则称 \(u\) 优于 \(v\)。
记 \(dis(u,v)\) 为 \(u\) 到 \(v\) 路径上的最大权值。对于每个点 \(u\)，我们考虑对于所有优于 \(u\) 的点 \(v\)，求出使得 \(dis(u,v)\) 最小的 \(v\)。记 \(f_u=v\)，且记 \(w_u=dis(u,v)\)。我们容易在 \(O(n^2)\) 的时间复杂度内求出所有的 \(f_u\) 和 \(w_u\)。
我们考虑对于初始状态 \(S\) 和目标状态 \(T\) 进行移动，我们希望每次移动后的势能减少。则每次移动选择某个状态的某个棋子，设其在编号为 \(u\) 的点上，则将其移动到 \(f_u\) 上。假设当前状态的势能为 \(X\)，则过程中会产生的最大势能为 \(X-h_u+w_u\)，移动后的势能为 \(X-h_u+h_{f_u}\)。我们对于所有不相同的 \(s_i\) 和 \(t_i\) 加入堆，按照 \(w_u-h_u\) 的顺序操作即可。
细节见代码，复杂度 \(O(nk \log k)\)。
谁家模拟赛把这个放 T2。