【听课记录】25.10-LCA-Week4

KSCD_ · 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 的序列形成双射，这也可以证明下面的结论。

下面是一些结论：

考虑 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] 在路上

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