典题乱做 1

1

P5547

数 $n$ 个点无标号无根树数：

• 每个节点是三种颜色之一：红，蓝，黄
• 红色节点度数不超过 $4$，蓝色和黄色节点度数均不超过 $3$
• 黄色节点不能相邻

$1\le n\le 3000$

强制重心为根，减去重心为边的情况。

设 $f_{i,0/1/2}$ 表示 大小为 $i$ 且根的颜色 $0/1/2$，根有一条边连出去。再设 $g_{i,0/1/2,0/1}$ 辅助转移，表示 大小为 $i$，$0/1/2$ 个子树，有没有黄色。

P4321

$n$ 个点的树上随机游走。$q$ 次询问从 $u$ 去到 $S$ 中所有点至少一次期望几步。

$n\le 18,q\le 10^5$

设 $d{p}_{S,u}$ 表示 在 $u$ 且要走完 $S$。

列出 $2^{n}n$ 个方程，对于 $d{p}_{S,\ast }$ 只会在同层或 $S^{\prime }<S$ 层转移，按 $S$ 从小到大消元。

P9262

$n\times m$ 的矩阵，有不同编号的滑块和空格。$q$ 次施加 上/左/下/右 的重力。求最后的位置。

$n,m\le 500,q\le 5\times 10^5$。

相对的方向做多次只用保留最后一次。同一种操作两两之间如果没有反向的操作，则后面一次无用。

去掉开头结尾 $O(1)$ 次操作后，四种操作以一个合法的顺序重复多次。开头处理若干步后所有的滑块都在某个角落。此时转一圈只改变每个滑块的位置，不改变整体的形状，是一个置换。

求出置换后，找出置换环后 $cy{c}_i\to cy{c}_{(i+k)\mathrm{mod}siz}$。复杂度 $O(nm)$。

P10559

$n$ 个点 $m$ 条边的无向图。保证在任何非空子图中，最小度数 $\le 10$。

初始有 $a_i$。$q$ 次操作：

• $a_x+v$
• 求 ${\sum }_{(u,v)\in E}{a}_v$。

$n\le 3\times 10^5,q\le 3\times 10^6$。

$O(1)$ 修改 $O(deg)$ 查询，或 $O(1)$ 查询 $O(deg)$ 修改。

拓扑排序，给图定向，使得每个点 $\le 10$ 个出度。修改和查询都只关心出边的贡献。

P10560

$n$ 个球，权值为排列 $p_i$。

$n$ 个点有根树，每个点能放一个球。

按 $1$ 到 $n$ 的顺序放球 $i$：

• 初始球在根。
• 如果当前位置已经有球，选择让球进入一个子树

使每个位置都有球，设 $a_i$ 表示第 $i$ 个顶点中球的值。最小化 $a$ 的字典序。

$n\le 5\times 10^5$