20200416 SCOI模拟1

A - 同桌与室友

相当于是有一张图，边有两种，与每个点相邻的每种边至多有一条。求有多少种重标号的方案，使得重标号前后的图相同。

由于每个点的度数不超过 2，我们可以对连通块的形态讨论（每个连通块要么是链，要么是环）。

记得取模。

B - 传送

Sol 1

这是我考场上的想法。

一个观察是，只需要保证两个相邻的点之间的边权大于等于两个点的点权差，就能保证方案合法，因为考虑在同一条链上的三个点 $A,B,C$：

$$\begin{aligned} dis(A,C) =& dis(A,B) + dis(B,C)\\ \ge& |a_A-a_B| + |a_B-a_C|\\ \ge& \left|\left(a_A - a_B\right) + \left(a_B - a_C\right)\right|\\ =& | a_A - a_C| \end{aligned}$$

对于每个点，求出 $L_x,R_x$ 表示当 $a_x \in [L_x,R_x]$ 时存在一种合法的给 $x$ 的子树内的点赋值的方案。

设 $w(u,v)$ 为 $u,v$ 之间的边的边权，则有转移方程

$$\begin{gathered} L_x = \max_{v\in son_x} \{ L_v-w(x,v)\}\\ R_x = \min_{v\in son_x} \{ R_v+w(x,v)\} \end{gathered}$$

一组 $\{[l_i,r_i]\}$ 是合法的当且仅当对于所有的 $x$ 都有 $L_x \le R_x$。

对于 $type=1$ 的，套个二分就可以了。

复杂度 $O(n\log V)$，我以为能过，但是只有70分。。。:ambulance:

Sol 2

我们不妨带上未知数进行 dp。假设花费的代价是 $v$，发现有了 $v$ 之后 $L_x,R_x$ 只不过就是变成了 $L_x - v, R_x + v$（因为 min 和 max 函数里面每一项都是原来的值 $+v$）。

所以当 $type=1$ 的时候，答案就是

$$\left\lceil \frac{\max\{ \max_{i\in [1,n]}\{ L_x-R_x\},0\}}{2}\right\rceil$$

C - 生成树

设 $A_{i,j}$ 为一个二元生成函数，$x^ay^b(a,b\ge 0, a+b\in [0,1])$ 的系数为从 $i$ 到 $j$ 的边中选出 $a$ 条绿色边、$b$ 条蓝色边的方案数。

根据矩阵树定理我们知道

$$\det(L_r) = \sum_{T\text{为生成树}} \prod_{(i,j)\in T} A_{i,j}$$

我们只要求出 $\det(L_r)$ 的各项系数就能得到答案。

把 $A_{i,j}$ 的点值带入求行列式，最后再插值回去，可以做到 $O(n^5)$ 的复杂度。

一种实现：由于最后多项式中 $x$ 的次数至多是 $n-1$，所以可以把 $y$ 带成 $x^{n}$，避开二维插值。

注意判掉输入的自环。