- 组题人：znstz, Crysfly
填写数字
来源：
排列计数
来源：
黑白棋子
来源：
不妨假设 $w\ge b$。
记 $mx_i$ 为删去 $i$ 之后剩下的连通块的大小最大值，那么假如 $w>mx_i$，则 $i$ 任意时刻必须是白色。
考虑当有点必须是白色时，答案就是把这些必须是白色的点删去后，剩下的大小超过 $b$ 的连通块个数。
否则，答案是 $1$ 或 $2$，而且为 $1$ 当且仅当存在某个点 $u$，删去 $u$ 之后存在两个连通块大小超过 $w$ 且存在另一个连通块大小超过 $b$。
我们记 $m=\min\{mx_i\}$，显然这个式子在重心处取到最小，所以我们以重心为根（有两个的时候就以那条边为根）。
当 $w\le m$ 时，没有点必须是白色，割掉一个点后最大的连通块一定是父亲的那个，所以记 $se_i$ 为儿子子树中的次大值，那么当 $b\le \max\{se_i\}$，答案是 $1$，否则答案是 $2$。
当 $w>m$ 时，必须是白色点的那些点形成了一个包含根的连通块，那么我们知道删去白色的点之后剩下的连通块一定是某个子树，那么一个子树是剩下来的连通块的条件就是 $mx_{fa_i}< w\le mx_i$，然后会所有 $b\le \min(w,sz_i)$ 有 $1$ 的贡献。
复杂度 $O(n)$。
冒泡排序
来源：
考虑枚举一个值 $V$，将序列中 $\ge V$ 的值看作 $1$，$< V$ 的值看作 $0$，将序列变成 $01$ 的形式。
对于所有的 $V$，求出对 $01$ 序列做完后区间内 $1$ 的个数，把这些答案相加就是总和。
发现对于一段后缀，它的每个 $0$ 每轮会向前移一格。一段前缀，如果有 $1$ 的话，一定会有 $1$ 交换到交界处。
那么对于一个值 $V$，我们询问的后缀 $[p,r]$ 新增的 $1$ 的个数其实是 $[p,p+k-1]$ 中的 $0$ 数与 $[l,p-1]$ 中的 $1$ 数取 $\text{min}$。
把暴力写出来，发现 $\text{min}$ 两边的贡献都是简单的主席树查询，取 $\text{min}$ 的情况也是简单的主席树二分，直接维护就好了。
时间复杂度 $O(n \log n)$。
数学公式炸了，删不掉了。
T3 比较自然的思路：
考虑手模样例，注意到当 $x=1,y=1$ 时答案是 $1$。不妨考虑什么时候 $f(x,y)=1$？
先考虑什么时候 $f(1,1)=1$？结论是当有一个三度点时就是 $1$，因为我们可以在这个三度点交换黑白两个点。
考虑 $x=y$ 时，什么时候 $f(x,x)=1$？结论是当有一个节点，它存在三个子树大小 $\ge x$ 时答案就是 $1$。
不难发现一般情况下，不妨令 $x\ge y$，当存在一个节点 $u$，它有两个子树大小 $\ge x$，一个子树大小 $\ge y$ 时，$f(x,y)=1$。
此时你已经会判 $f()=1$ 的情况了。那么不难发现对于一个固定的 $x$，令 $x\ge y$，使得 $f(x,y)=1$ 的 $y$ 是一个前缀。
不难处理出 $g_x$ 表示最大的 $y$ 令 $f(x,y)=1$（不要忘了我们固定了 $x\ge y$），那么我们可以处理出所有 $f(x,y)=1$ 的答案和，这可以在 $O(n)$ 内做到。
那么剩余情况，一定就有 $f\neq 1$ 了。枚举 $x$ 和 $y\in(g_x,x]$，怎么计算 $f(x,y)$ 呢？因为 $f\neq 1$，所以两个颜色的棋子一定不能交换。继续手模样例，当存在一条边 $u-v$，$u$ 这端 sz $\ge x$，$v$ 这段 sz $\ge y$，而且 $u$ 的每个子树（不包含 $v$）的 sz 都 $\lt x$（也就是不能把 $x$ 完全塞到一个子树中，也就是 $x$ 这个点一定会占领 $u$，$y$ 一定过不来），那么这就是一种情况，令答案 $+1$。然后你写出这个的 $O(n^3)$ 代码，然后发现样例过了。
然后你发现你可以计算出对于一个 $x,u$，合法的 $y$ 的范围，然后答案就会加一个 $x\times $ 等比数列。现在就是 $O(n^2)$ 的。
然后你发现枚举一个 $u$，然后合法 $x$ 也是一个范围，我们计算出这个范围，然后做一些 dirty work 就做到 $O(n\log n)$ 了，瓶颈在于 dirty work 时实现不好拆出了一个前缀加单点查需要树状数组 /gg。
啊总之你写出之前的那个 $O(n^3)$ 然后慢慢优化就可以过了。