11.18 联测

怎么今天打 Div2 啊。

Div1 T1

求一棵树所有编号区间导出子图的连通块数之和。

扫一遍 $i$，统计以 $i$ 为左端点的区间的答案之和。维护 $ans_x$ 表示 $[i,x]$ 的答案。

先暴力求出 $i=1$ 的 $\{ans\}$，考虑删除一个数对连通块数的影响。

发现删除 $u$ 会使连通块数增加 $d_u-1$，$d_u$ 表示 $u$ 的度数。

也就是说 $\{ans\}$ 的变化是：一段 $-1$，一段 $+0$，一段 $+1$，一段 $+2$，以此类推。

发现这样的区间数为 $deg_u$，$deg_u$ 表示 $u$ 在原图上的度数。所以总区间数 $O(n)$。

Div2 T1

发现严格大于和严格小于是对称的，我们只需把总方案减去相等的方案再除以二即可。

现在我们要统计长度为 $n$ 的排列 $\{a\}$，使得 $a$ 的逆排列还是 $a$。

设 $f_i$ 表示 $n=i$ 时的答案。

• $a_i=i$，此时从 $f_i \larr f_{i-1}$。
• $a_i<i$，此时在 $[1,i)$ 中选择一个数跟 $i$ 配对，此时 $f_i \larr f_{i-2} \times (i-1)$。

Div2 T2

发现一个点的深度就是他的 $popcount$。

考虑在把贡献挂在 $u$ 的祖先上，然后容斥。

令 $f(u,i)$ 表示 $u$ 子树距离 $u$ 为 $i$ 的点有几个。

设 $u$ 的深度为 $x$，那么 $f(u,i)=\binom{x}{i}$。

Div1 T2

把全部点按颜色排序。

颜色 $c-1$ 向颜色 $c$ 转移：$f_{i,j} \larr f_{x,y}+|i-x|+|j-y|$。

第一维按 $x$ 值排序扫描线解决，第二维用线段树解决。