CF1606F Tree Queries

## CF1606F Tree Queries 提供一个比较偏套路的做法。（类似集训队作业 三角形） 先考虑只有全局询问。 首先 $ k $ 从大到小处理，那么对于固定的 $ u $ ,最优方案删掉的点数肯定是不降的。 考察一个点 $ u $ ，在当前 $ k $ 下答案为 $ f_u $ .若 $ f_u -1-k\ge 0 $ 那么 $ u $ 的父亲 $ fa $ 的最优方案就会删掉 $ u $ .进一步的，对于更小的 $ k $ 和任意的点 $ v $ ,要么不删 $ fa $ ，要么同时删掉 $ fa $ 和 $ u $ .那么我们就可以将 $ u,fa $ 直接合并，然后 $ f_{fa}\leftarrow ^+ f_u-1-k $ . 这里还有一个问题是， $ k $ 每次变化， $ f $ 都会改变。考虑另记录一个 $ cnt_u $ 表示 $ u $ 的最优决策中删掉的点数，然后真正 $ u $ 的答案是 $ f_u -cnt_uk $ .（当然，合并的时候就变成 $ f_{fa}\leftarrow^+ f_u-1,cnt_{fa}\leftarrow^+ cnt_u+1 $ ） 剩下的就套路了，发现 $ u $ 和 $ fa $ 会在 $ k\le \frac{f_u-1}{cnt_u+1} $ 时合并。用一个`std::set`维护即可。这样就能求出全局的答案。 这样无法求出任意点的答案是因为已经被合并掉的点信息不会被更新。令 $ u $ 为当前点， $ r $ 为 $ fa $ 所连通块的根，对 $ u\rightarrow r $ 这条链（含 $ r $ ,不含 $ u $ )链加即可，询问就是单点询问。可以用树状数组维护。 复杂度 $ \Theta(n\log n) $ .[my code](https://codeforces.com/contest/1606/submission/134983700) 一个问题：在链加的时候直接暴力加 $ u\rightarrow r $ 这条链，也能过，而且比用树状数组快，是数据没卡还是有合理的复杂度分析？目前我怀疑有一个常数很小的自然根号在。[brute code](https://codeforces.com/contest/1606/submission/134980496)