https://atcoder.jp/contests/abc267
全部的 AC 代码：
E
题目要求最小化花费，而花费是所有花费的最大值，故考虑二分，记现在二分的值 \(mid\) 为 \(lim\)。
因为每次代价都是与删点所连点的边权和，所以尽量去找当前花费 \(\leq lim\) 的，找不到当然就继续去二分更大的值。
因此，我们可以执行一个 \(\tt{bfs}\)，每次找花费 \(\leq lim\) 的点进行扩展，并在扩展当前点的同时对其邻点更新花费（也就是减去当前点权），当临点更新后花费 \(\leq lim\) 时入队。
F
由于需要求 \(u\) 点跳 \(k\) 步能够到达的树上的点，故尽可能找到 \(u\) 能够跳到的最远点，因为如果 \(u\) 跳到最远点都不足 \(k\) 步，那么必然无解。
什么点可能成为距 \(u\) 的最远点呢？直观的想法是直径的两个端点 \(x, y\)。
证明：
不妨设 \(dis(u, x)\geq dis(u, y)\)。
假设能够找到点 \(v\) 使得 \(dis(u, v)> dis(u, x)\)，那么找到 \(u\) 到达路径 \(x, y\) 上的点 \(u'\)。
我们有 \(dis(u', v)>dis(u',x)\)，故 \(dis(u', v)+dis(u', y)=dis(v, y)>dis(u', x)+dis(u', y)=dis(x, y)\)，与 \(x, y\) 为直径矛盾。
证毕。
下面的做法很简单：
就分别以 \(x, y\) 为根节点，求出 \(u\) 的 \(k\) 级祖先即可。
G
为了方便转移，对所给序列 \(w\) 进行升序排序。
容易想到状态表示 \(f[i, j]\) 为前 \(i\) 个元素共有 \(j\) 个位置 \(pos\) 满足 \(w_{pos}<w_{pos+1}\)。（记为顺序位置）
考虑 \(f[i, j]\) 如何转移到后面的状态。
对于第 \(i+1\) 个元素 \(w_{i+1}\)，可以发现当插入 \(w_{i+1}\) 时（也就是将 \(w_{i+1}\) 挑选 \([1, i+1]\) 一个位置放入），要么会使原来的顺序位置个数不变，要么比原来多 \(1\)。
-
对于不变的情况，有多少种方案呢？
- 首先，插入位置 \(1\) 肯定不变，有一种。
- 插入到与 \(w_{i+1}\) 等值的元素（记这样的元素有 \(cnt\) 个）后面，有 \(cnt\) 种。
- 插入到已经产生的顺序位置 \(pos\) 的后面（也就是插入 \(pos, pos+1\) 之间），有 \(j\) 种。
因此，\(f[i, j]\) 对 \(f[i+1, j]\) 的贡献为：\(f[i+1, j] += f[i, j]\times(1+cnt+j)\)。
-
比原来多 \(1\) 的情况就是不变情况的补，即有 \(i+1-(1+cnt+j) = i-j-cnt\) 种，
因此，\(f[i, j]\) 对 \(f[i+1, j]\) 的贡献为：\(f[i+1, j+1] += f[i, j]\times(i-j-cnt)\)。
EX
注意到值域很小，所以直接将答案拆奇偶然后进行 NTT 分治来合并背包即可。
记当前区间 \(u\) 取奇数个物品的背包为 \(u_{o}\)，偶数个的为 \(u_{e}\)，左右子区间分别记为 \(ls, rs\)。
分治过程即：
\[u_o = merge(ls_e, rs_o) + merge(ls_o, rs_e) \\ u_e = merge(ls_e, rs_e) + merge(ls_o, rs_o) \]\(merge\) 用 NTT 卷积即可。
标签：AtCoder,cnt,Beginner,rs,pos,merge,267,ls,dis From： https://www.cnblogs.com/Tenshi/p/16659253.html