本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-19 08:27:14

10.15 树上问题

• 连通块

特殊情况：路径、邻域（邻居）。

统计方式：按 LCA 分类（树上启发式合并）、按分治中心分类（树上分治）、连通块性质（点边容斥）。

• 虚树

点之间的拓扑关系。

P7735 [NOI2021] 轻重边

题意

给定一棵树，初始全为轻边。修改给出 $x,y$，将该路径上的边改为重边，路径上的点直接连接的其他边改为轻边，查询求 $x,y$ 路径上的重边数量。多组数据，$T\le 3,n,q\le 10^5$。

题解

需要用支持路径修改的方式刻画重边，考虑每次将路径覆盖为同一个值 $i$，于是重边定义为两端值相同的边，其余为轻边。注意到只要初始值和每次操作的值两两不同，这样的定义就是正确的。于是直接树剖 + 线段树维护路径覆盖，求路径上相邻相同值的对数即可，复杂度 $\mathcal O(q\log ^2n)$。

另一种做法是考虑轻重边转化的次数，注意到一条边 $(u,f)$ 为重边需要某次操作的两点分别在 $u$ 子树内外，而改回轻边需要存在 $u$ 的兄弟 $v$，使得某次操作的两点分别在 $v$ 子树内外。这样改回轻边的次数与树上启发式合并的复杂度同级，为 $\mathcal O(n\log n)$。

于是需要支持路径改为重边，快速查询路径相邻的轻边位置并单点修改。好像可以直接存每个点到根第一条轻边，再把原树每条重链所挂的当前重边存下来。具体没有实现，不管了。

P9886 [ICPC 2018 Qingdao R] Kawa Exam

题意

给定一张无向图，每个点有颜色 $a_i$，对每条边求将其断掉后所有连通块同种颜色的最大出现次数之和。多组数据，$n,m\le 10^5,\sum n,\sum m\le 10^6$。

题解

原图的答案容易求，显然若连通情况不变，则最终答案也不变，于是只有断掉割边会改变答案。可以先将每个边双缩成一个点，形成一个森林，变成求断开森林中某条边后的答案。设 $f_u$ 表示 $u$ 子树的答案，$h_u$ 表示 $u$ 所在树除掉 $u$ 子树的答案，则 $u$ 点连向父亲的边断开的答案为 $res-f_{rt}+f_u+h_u$，其中 $rt$ 表示 $u$ 所在树的根节点。

现在需要求出 $f,h$ 两个数组，考虑使用树上启发式合并，依次求出所有轻儿子的答案并清空信息，最后求重儿子的答案并保留信息，再暴力将轻儿子的信息全部加入求当前点的答案，这样的总复杂度是 $\mathcal O(n\log n)$ 的。注意轻重儿子的划分需要用子树内的原图点数，不能用缩点后的点数，否则复杂度没有保证，这是因为每次增删信息需要枚举原图的所有点。细节较多，一遍过了，爽。

P5411 [SNOI2019] 网络

首先一定会选一个直径不超过 $d$ 的连通块，于是需要对每个点求以其为中心的连通块总延迟。这个需要启发式合并和长剖？反正难写完了，遂弃之。

• 直径

P4220 [WC2018] 通道

有随机化做法，即每次对一个点找最远点，重复足够多遍即可取到答案。确定性做法的话先考虑两棵树，此时对第一棵树边分治，将该轮考虑到的点在第二棵树中建出虚树，带上第一棵树中到分治中心距离的权，在上面 DP 即可。三棵树时再套一层分治，比较难写。之后学了边分树应该会写。

10.17 图上的树

• DFS BFS 树

放到图论里讲。

• 最小生成树

P4208 [JSOI2008] 最小生成树计数

题意

给出一张 $n$ 点 $m$ 边的带权无向图，求其权值和最小的生成树个数。$n\le 100,m\le 1000,w_i\le 10^9$，保证同一种 $w_i$ 的边数不超过 $10$。

题解

考虑 Kruskal 的过程，即依次考虑每种权值，并在不成环的前提下加尽可能多的边，且考虑到某种权值时连通情况是固定的。对每种权值将之前形成的每个连通块看成一个点，求连边数量最多且不成环的方案数。由于同种权值边数 $c_i$ 不超过 $10$，可以直接 $2^c$ 枚举，总复杂度大概 $\mathcal O(m\log m+2^cm)$。

如果没有同种边数量的限制，可能需要矩阵树定理解决，不会，摆了。

QOJ9904 最小生成树

题意

给定 $a$ 序列，$n$ 个点的完全图上 $(i,j)$ 边权为 $a_{i+j}$，求该图的最小生成树。$n\le 2\times 10^5,a_i\le 10^9$。

题解

考虑 Kruskal 的过程，于是先对和 $x$ 按 $a$ 从小到大排序，之后依次处理和固定的每种边。由于连边次数为 $n-1$，只需要快速找出需要连的边即可。注意到事实上是对 $[1,x-1]$ 和其左右翻转后的序列对应位置连边，这启发我们维护所在集合并寻找不同位置。

具体地，使用启发式合并的并查集实时维护所在集合，总复杂度 $\mathcal O(n\log n)$。使用树状数组维护正反哈希值，可二分出第一个不同位置，总复杂度 $\mathcal O(n\log ^2 n)$。由于并查集修改时树状数组要同步修改，此时修改的总复杂度也是 $\mathcal O(n\log ^2n)$。

事实上，如果只讨论修改，使用线段树同时修改 $m$ 个节点的复杂度为 $\mathcal O(n\log \frac nm)$，或许能分析到单 log 的总复杂度。不过不同位置很难在线段树上二分，查询复杂度不好降低，不管了。

QOJ4784 最小方差生成树

先拆一拆式子，根据方差的性质，将平均值替换成其他值一定不优。所以枚举平均值 $x$ 后用新的边权跑最小生成树，一定能取到答案，且不会比答案更优。然而本题还需要 LCT 之类的科技，所以弃了。

CF1550F Jumping Around

题意

数轴上有 $n$ 个点 $a_i$，只能在这些点之间移动，$i,j$ 点可直接到达当且仅当 $d-k\le \left|a_i-a_j\right|\le d+k$。给定 $d,s$，每次询问给出 $t,k$，求以 $d,k$ 为参数时 $s$ 是否能到达 $t$。$n,q\le 2\times 10^5,a_i\le 10^6$。

题解

考虑图论建模，以能使两点直接相连的最小 $k$ 为边权。注意到这样建图后走最小（瓶颈）生成树上的边一定最优，于是目标变成求该图最小生成树，再求路径最大值与给定 $k$ 比较即可。同时起点固定，甚至只需要一遍 DFS 即可求出所有路径最大值。

由于是完全图，考虑 Boruvka 算法，需要求某个集合内连向集合外的最小边。由于边权为 $\left|\left|a_i-a_j\right|-d\right|$，推一推发现距 $i$ 点连的最小边是离 $a_i-d$ 或 $a_i+d$ 最近的 $a_j$。于是用 set 维护所有的 $a_j$，处理当前连通块时将其内部的 $a_i$ 从 set 中删去再查询，总复杂度 $\mathcal O(n\log ^2 n)$。

LOJ6631. 「EC Final 2018」异国情调的……古城

上课没咋听懂，但感觉不是特别难且好题，之后应该会补。

• 基于树的特殊图

外平面图：存在一个面与所有其他点都相连。此时除这个面外，其余面对偶图为树。

广义串并联图：可通过串并联结构缩成树。

弦图：图中任意超过三个点环中均存在至少一条弦的图。也可以用树上的连通块等价定义，以某个连通块为点，两个点连边当且仅当对应的两个连通块有公共点。

AT_joisc2017_f 鉄道旅行 (Railway Trip)

建模成图后在上面倍增，应该是好题，之后应该会做。

10.17 思考题 前 k 小问题和最小扩展过程

最小扩展过程

对于某些求第 $k$ 小方案的问题，将方案之间的关系建成树，边权为方案权值的差值，若满足以下几个条件，即可用最小扩展过程求解。

• 每种方案对应且唯一对应树上某个节点。
• 边权非负（即子节点权值不低于父节点）。
• 每个点的出度足够小。
• 每种方案可用足够少的信息刻画。

其中前两条保证正确性，后两条保证复杂度。若均满足，则以根节点为起始状态加入堆，每次从堆中取出最小权值，再加入其所有子节点方案即可。每个点出度不超过 $c$ 时复杂度为 $O(ck\log ck)$。

以上是完成了下面内容后的总结，下面是思考题的具体内容，似乎全都忽略了排序复杂度，不管了。

• I. 给定两个 / 三个数组，求每个数组内选一个数求和后的第 $k$ 小值。

二分答案 $x$，双指针求不超过 $x$ 的个数来 check，复杂度 $\mathcal O(n\log V)$。三个数组时枚举前两个数组再双指针，复杂度 $\mathcal O(n^2\log V)$。

若 $k$ 较小，对每个 $i$ 维护当前指针 $j=p_i$，堆中维护 $n$ 个元素 $a_i+b_{p_i}$，每次取最小并更新指针，复杂度 $\mathcal O(k\log n)$。三个数组时先对 $a,b$ 求出前 $k$ 小数组 $t$，再对 $t,c$ 求第 $k$ 小，后一遍对每个 $c_l$ 维护指针，复杂度 $\mathcal O(k\log n)$。

• II. 给定 $n$ 个非负整数，求前 $k$ 小子集和。

考虑一个搜索过程，若当前状态为 $S$，最后一个 $1$ 在 $p$，则可以从 $[p+1,n]$ 中随便找一个拓展并更新 $p$，只记录 $p$ 和权值即可。容易发现该过程形成一棵树，且满足开头所说的限制，直接套用做法即可。由于每个点最多有 $n$ 个子节点，复杂度 $\mathcal O(nk\log (nk))$。

为了降低度数，对整棵树进行左儿子右兄弟变换转成二叉树，发现新树的实际意义为加入 $p+1$ 或删去 $p$ 再加入 $p+1$，分别为连向第一个儿子和兄弟，同样维护即可，时间复杂度 $\mathcal O(k\log k)$。

• III. 给定 $n$ 个非负整数，求大小为偶数的前 $k$ 小子集和。

同样先建出暴力转移，每次选 $[p+1,n]$ 中任意两个元素扩展并更新，每个点最多有 $\mathcal O(n^2)$ 个子节点，复杂度 $\mathcal O(n^2k\log (nk))$。

同样需要将出度减小，考虑每向外扩张两个时依次确定两个元素的位置，则需加一维 $0/1$ 记录 $p-1$ 是否被选。$p$ 可选上 $p+1,p+2$ 扩展到 $(p+2,1)$；若 $p-1,p$ 均被选，则可由 $(p,1)$ 改为 $(p+1,1)$，这是确定第一个元素位置；也可以直接将 $p$ 改为 $p+1$ 变为 $(p+1,0)$，即已确定第一个元素，开始单独移动第二个元素。可以发现仍然满足开头所说的条件，复杂度降为 $\mathcal O(k\log k)$。

• IV. 给定 $n$ 个非负整数，有黑白两种颜色，求黑色元素个数为偶数的前 $k$ 小子集和。

直接分成黑白两部分，白色跑 II，黑色跑 III，分别求出前 $k$ 小子集和，之后使用 I 中 $k$ 较小时的做法合并起来即可。由于每一步都是 $\mathcal O(k\log k)$ 的，总复杂度也是 $\mathcal O(k\log k)$ 的。

• V. 给定 $n$ 个非负整数，求大小为 $m$ 的前 $k$ 小子集和。

最小的初始状态为前 $m$ 小的和，于是考虑从后往前依次确定每个元素的位置。令状态 $(x,y,z)$ 表示前 $x$ 个数没动过，第 $x+1$ 个数目前是第 $y$ 小，第 $x+2$ 个数为第 $z$ 小，这是用来限制 $y\lt z$ 的。$(x,y,z)$ 可转到 $(x,y+1,z)$ 或 $(x-1,x+1,y)$，可以发现边权非负，时间复杂度 $\mathcal O(k\log k)$。

P2541 [USACO16DEC] Robotic Cow Herd P

题意（VI）

给定 $n$ 个长分别为 $m_i$ 的数列，求每个数列各选一个数的前 $k$ 小和。$n,k\le 10^5,m_i\le 10$。

题解

初始状态为每个数列最小值加起来，考虑依次确定每个数列所选的数。令状态 $(x,y)$ 表示 $x$ 之前的数列已确定选法，当前 $x$ 数列选第 $y$ 小，$x$ 之后的数列全都选最小。转移有 $(x,y)$ 转到 $(x,y+1)$，表示选更大元素，边权 $a_{x,y+1}-a_{x,y}$；转到 $(x+1,2)$，表示确定第 $x$ 行选 $y$，开始拓展第 $x+1$ 行，边权 $a_{x+1,2}-a_{x+1,1}$；另外当 $y=2$ 时可令第 $x$ 行选最小，即可以直接转到 $(x+1,2)$，边权 $(a_{x+1,2}-a_{x+1,1})-(a_{x,2}-a_{x,1})$。

不管是考虑实际过程还是看上面的边权，都需要 $a_{x,2}-a_{x,1}$ 不降，于是按照这个将 $m$ 个数列排序即可。可以发现满足所有要求，于是这样做是对的，复杂度 $\mathcal O(k\log k)$。

另外，Pigsyy 指出不选最小值的数列不超过 $\log k$ 个，这是由于若 $c$ 个数列选了非最小值，则权值不超过其的选法至少有 $2^c$ 种，而这不应该超过 $k$。然而没有想出用这个做的简单方法。

P6646 [CCO 2020] Shopping Plans

题意（VII）

给定 $n$ 个长分别为 $m_i$ 的数列，每个数列选数有个数限制 $[l_i,r_i]$，求满足限制的选数方案中前 $k$ 小的。$n,k,\sum m\le 2\times 10^5$。

题解

V 是 $n=1,l=r$ 的情况，先考虑拓展到 $l\le r$。在 V 做法的基础上，初始状态为 $(l-1,l,m_i+1)$，之后对形如 $(x-1,x,m_i+1)$ 且 $x\lt r$ 的状态新增转移 $(x,x+1,m_i+1)$，表示直接将选的数量增加 $1$ 即可。

再考虑对 $n$ 个数列做，注意到 IV 是 $n$ 个数列各选一个数的情况， 于是定义每个数列对应的新数列为其原数列所有选法的值，对新数列做 IV 即可。由于每个新数列被用到的元素不会太多，可以用多少求多少，复杂度得到保证，应该还是 $\mathcal O(k\log k)$ 的。

10.19 树上问题

Prufer 序列

考虑将有标号无根树扔到一个序列上，方式为每次找到编号最小的叶子节点，将其删去，并将其连接的点编号加入序列。这样操作直到只剩两个点，可得到一个长为 $n-2$ 的序列，即为 Prufer 序列。

该序列有一些性质，最后剩的点中必然包含 $n$，同时每个点在树上的度数为其在 Prufer 序列中出现次数加一。

根据 Prufer 序列也可以还原出一棵树， 方式是找到当前度数为 $1$ 的最小编号，它一定与序列开头元素连接，确定该边并将两点度数均减 $1$。以此类推即可还原整棵树，最后把剩余两点连起来即可。

这两个过程也是模板题的内容，实现上需要维护指针，指向当前度数为 $1$ 的编号最小的点，操作之后若其指向的点编号较小且度数降为 $1$，就直接继续操作，重复该过程直到度数不为 $1$ 或编号较大。根据两个过程，可以发现 $n$ 个点的有标号无根树与长为 $n-2$，值域为 $n$ 的序列形成双射，这也可以证明下面的结论。

下面是一些结论：

• $n$ 个有标号点，无根树有 $n^{n-2}$ 种（Prufer 序列可证），有根树有 $n^{n-1}$ 种（前者定根）。
• $n$ 个有标号点，有根树森林有 $(n+1)^{n-1}$ 种，方式是将所有根连到超级根 $n+1$，相当于 $(n+1)$ 个点的无根树种类数。
• $n$ 个左部点 $m$ 个右部点的完全二分图，生成树个数为 $n^{m+1}\times m^{n+1}$。

考虑 Prufer 序列的生成过程，每个位置删点时方案数为对面的点数，而且属于哪一部分是自然钦定的，不用乘组合数，且最终剩的一条边也一定在两部分之间，于是可以得到上式。

• 引理：$n$ 点有标号无向图有 $k$ 个大小为 $s_i$ 的连通块，连 $(k-1)$ 条边使其连通方案数为 $n^{k-2}\cdot \prod_{i=1}^k s_i$。

设 $d_i$ 表示 $i$ 连通块连的边数，有 $\sum d_i=2k-2$。根据 Prufer 序列性质，每个点在序列中的出现次数 $e_i=d_i-1$，有 $\sum e_i=k-2$。枚举 $e$ 序列计算，答案为 $\sum_{e_i\ge0,\sum e_i=k-2}{k-2\choose e_1,e_2,\cdots,e_k}\times \prod_{i=1}^k s_i^{e_i+1}$，提出 $\prod_{i=1}^k s_i$ 后剩余部分为多元二项式定理，为 $(\sum s_i)^{k-2}=n^{k-2}$，于是结论得证。

P11039 【MX-X3-T6】「RiOI-4」TECHNOPOLIS 2085

虚树相同，用上 Prufer 序列的推论计数，之后应该会写。

• 树同构

P8499 [NOI2022] 挑战 NPC Ⅱ

很树同构的题，之后应该会做。

P9056 [集训队互测 2022] 在路上

随机选两点时重心在路径上的概率不低于一半，于是随机选之后通过某种方式在链上找中心，再判断是否是全树重心。之后应该会做。