cf1606F

题意

Link

---

1. 考虑询问 \((x,k)\) 等价于以 \(u\) 为根，每个点 \(v\) 权值 \(\mathrm{child}(v)-k-1\)，找出 \(u\) 所在的连通块，权值最大的。
2. 如果固定 \(k\) 有很 simple 的 dp。
3. 考虑我们必定以权值为正的结尾，所以考虑建出权值 >=0 的虚树，其中虚树大小是 \(\mathcal{O(n)}\) 级别。 考虑 \(\mathrm{val}(x)=\mathrm{child}(x)-k-1\geq 0\)。 \(k\leq \mathrm{child}-1\)，这样 \(\sum_k{\mathrm{val}(k)\geq 0}=\mathcal{O(E)}=\mathcal{O(n)}\)
4. 这样dp便很显然了。