集训之图论专题

A

题意简述

给你一幅图，求割点，割边，极大点双连通分量数以及其边数

题目分析

模板题。割点数注意特判根结点以及去重。

注意图可能不连通

普通割点判断条件：low[v] >= dfn[u]

桥判断条件：low[v] > dfn[u]

极大点双连通分量在求割点时统计即可

而其边数可以将极大点双连通分量分组，然后暴力统计组内点之间的连边有多少即可

B

题意简述

求树上两点之间的最短距离

题目分析

dfs 求出每个点的层数，然后写个求解 lca 算法（倍增，st 表，树链剖分等）。

dep[x] + dep[y] - 2 * dep[getLca(x, y)] 即是答案。

C

题意简述

给你一张 $n$ 个点，$m$ 条边的无向图，求 $1$ 到 $n$ 的第 $k$ 短路。

题目分析

题目 $n \le 5 \cdot 10^3$，$k \le 5 \cdot 10^5$，用 $A^*$ 算法显然会超时，考虑更优的算法。

先建立一个反图，求反图上的最短路径生成树。对于树上每个点用可持久化可并堆维护信息：当前点到根节点（终点）的路径上经过的点所有的非树边（可以到达树中其他结点，但不是树边），后续将用这些边来推得第 $k$ 短路。

考虑 $k$ 为 $1$ 的情况，显然反图求得的 $dis[s]$ （dis 为最短路，$s$ 为起点），即为答案。

而 $k$ 不为 $1$ 时，求 $k$ 短路的过程，其实就是替换更劣的非树边或者是增加非树边的过程。

具体来讲，可并堆维护的信息有根节点（原结点到可并堆结点的映射），堆结点的左右儿子，左偏树的 dis 信息以及左偏树结点的信息（其实就是当前的答案以及最后一条边的信息，包括边的贡献以及终点）。

一条非树边的贡献可以记作 $w + dis[v] - dis[u]$，即边权加上终点的 dis 值，再减去原来的起点 $u$ 的 dis 值。

利用这个贡献，利用可并堆维护，利用有限队列取出最小的改变，再进行上述两种操作再加入优先队列中即可完成 $k$ 短路了（。

D

题意简述

给你一颗 $n$ 个点的树和一个数 $k$，对于每个结点 $u$ 求满足 $lca(x, y) = u$ 且 $(a_x + a_y + u) \equiv 0 \bmod k$ 的数量。

题目分析

考虑到题目信息很好用桶统计，考虑 dsu on tree。

每次对于一个结点 $u$，先暴力处理轻儿子并不保留信息，再考虑重儿子并保留信息，再加入轻儿子的影响即可。具体是指用桶存对于子节点在模 $k$ 意义下的所有余数数量。扫描一个子树时，再统计当前结点与前面子树或根节点对根节点的答案的贡献即可（此时需要不加入当前子树的值）。等完全扫描完当前子树，再加入当前子树的影响。

因为修改是 $O(1)$ 的，所以复杂度即是 dsu on tree 的复杂度 $O(nlog(n))$。

E

题意简述

给你一棵 $n$ 个点的树，求一个点到其他点的最大距离最小，若有多个点则全部输出。

题目分析

可以转化为求每个点到其他点的最大值是多少，可以考虑树上 DP。

两次 dfs，第一次统计当前结点到子树结点的距离最大值为多少。并且求出自己的重儿子（指有距离最大值的点在哪个儿子子树中）和第二重儿子。第二重儿子用于之后对重儿子的递推，重儿子用于之后对其他儿子的递推。

第二次 dfs，要传参从父亲结点而来到当前结点的最远距离是多少，这和当前结点到子树结点的最远距离共同组成了当前节点到其他结点的最远距离。而传此参数就需要刚才重儿子与第二重儿子参数。

F

题意简述

$n$ 个点，$m$ 条边，每个点有不同类型，共有 $k$ 个类型，每个类型只能有一个关键点。询问是否存在一种选择关键点的方案，使所选择的关键点能覆盖所有边。

题目分析

$n$ 个点，每个点都只有选与不选两个状态，然后还有一些约束有些点选了，有些点就不能选，这是典型的二分图问题。

边的影响很好考虑，如果边的一个点没选，则另一个一定会选，令有边 $(u, v)$，则在二分图中有边 $(\lnot u, v)$ $(\lnot v, u)$。

而还有类型的影响，同一个类型视为一个集合，即是集合中的一个点向集合中其他非点连边。直接连边的复杂度是不可接受的。考虑建边优化。可以选择前缀和建边优化。

具体是指给每个点抽象一个前缀点用于辅助，而对于每个非点抽象一个后缀点用于辅助。

前缀点之间向前连边，后缀点向后连边。再将点和抽象点连边。再处理原点和原点的抽象点 与 非点和非点的抽象点 之间的连边即可。其中的一对边如下：

建立完成连边，跑二分图即可。具体是跑 tarjan 求强连通分量，如果原点和非点属于同一个强连通分量（即形成了一个环），意味着有冲突，就是无解的情况。

G

题意简述

给你 $n$ 个点，$m$ 条边，每个点有一个权值 $a_i$，每个边也有一个权值 $w_i$。对于每一个点，如果自身权值大于自身连接的边即可向外扩展并且增加扩展的点的权值，求扩展之后，扩展的点中小于该点的权值有多少，大于该点的权值有多少。

题目分析

考虑构建一棵 Kruskal 重构树。构建重构树时，统计两个量，一个量是子树的所有原点的权值之和。另一个量是连接两个子节点的边权。显然，如果子树的权值之和大于父节点存储的边权，那么代表可以向上扩展，可以扩展父节点的所有子树结点。而统计叶子结点最终可以到达哪个位置可以在 dfs 中从上到下 $(O(n))$ 处理得到。

现在已知每个点可以扩展到哪些结点，关键是如何统计答案。因为 Kruskal 重构树的结点构建时满足 dfs 序，所以可以用树状数组表示一个区间。

所以对每个询问（结点）排序（按照结点的权值大小，因为是查询大于和小于当前结点的数），此顺序也是添加进入树状数组的顺序。具体是维护两个树状数组，一个统计小于数量，一个统计小于等于的数量（容斥即可得到大于的数量）。同时维护两个指针，当到达一个新的询问时，即移动两个指针到小于的位置和小于等于的位置，并且将位置信息添加到树状数组中，然后统计指定用 dfs 序统计子树中结点的数量即可得到答案。

H

题意简述

$n$ 个点，$m$ 条边，将图中的点划分成两个部分，每个部分中的点形成一个完全图，并且使两个部分的大小差最大。

题目分析

一些点能形成完全图，即代表这些点在原图中两两有边，即在补图中两两无边。即如果可以划分成两个完全图，也就意味着在补图中能形成两个集合，每个集合中的点两两无边，这即是典型的二分图图形。而原题中的无解即是对应不能形成二分图；原题中的两个部分的大小差最大即是将每个不连通的二分图中较大的放在一起，较小的放在一起。

综上，建立补图，用染色法跑判断是否二分图，并记录每个联通块的染色大小即可，每个联通块的染色的差值大小的绝对值之和即是答案。

I

题意简述

$n$ 个点，$m$ 条边，求最大流，并用最大流计算一个答案。

题目分析

裸的最大流，用 dinic 算法跑即可。

J

题意简述

给你 $n$ 个点，$m$ 条边，求欧拉路径的最后一条边。

题目分析

考虑欧拉路径的判断条件。

如果所有点的度数都是偶数，那么显然所有边都可以作为最后一条边。

如果有两个点的度数是奇数，那么显然只有这两个点的边可能产生贡献。考虑哪些边可能产生贡献，显然割边作为连接不能最后遍历。

但要注意一个 corner case，两个点只有一条连边时是可行的。

其他情况则没有欧拉路径，当前也没有答案。

同时此题还要注意重边对割边的影响！以及答案去重！

K

题意简述

$n$ 个点，$m$ 个类型，同类型点之间边权值为 $v_i + v_j$，不同类型点之间边权值为 $\left|v_i - v_j\right|$，求最大生成树。

题目分析

两个结论题解已经给出，关键是如何证明两个结论（似乎好像都没说清楚。

---

首先证明第一个结论：

假设 $a$，$b$，$c$ 三个点为同类点，权值从上至下依次递减，有边 $(b, c)$。

1. 若无边 $(a, c)$

   显然将树上边 $(b, c)$ 替换成边 $(a, c)$ 更优。

2. 若有边 $(a, c)$

   显然将树上边 $(b, c)$ 替换成边 $(a, b)$ 更优

综上，第一个结论成立。

---

再证明第二个结论：

证明之前先证明两个子结论：

1. 最大点（x）和最小点（y）一定有边连接

   1. 若是同类点，则由最大生成树一定包括最大边可得。
   2. 若不是同类点，则考虑树上最大点和最小点路径上与最大点连接的 $u$ 和 与最小点连接的 $v$（$u$ 和 $v$ 可能相同），考虑 $u$，至少与最大点和最小点中的一个类型不同，不妨令是最大点，则 $(x, u)$ 可替换为 $(x, y)$。

   综上，最大点和最小点一定有边连接

2. 一个点与最大点或最小点（取决于距离哪个点更远）的连接方式要么是通过同类点中的最大点间接相连（同类最大点即是全局最大点则是直接），要么是直接相连

   反证。不妨令点 $a$ 与最大点 $x$ 是通过不同类点 $b$ 相连，显然 $(a, b)$ 可以替换为 $(a, x)$。得证。

再正式开始证明第二个结论：

若 $c$ 为最大点，$d$ 为最小点，$a$ 和 $b$ 有边相连，$b$ 与最大点 $c$ 距离更远。

根据第二个子结论，$b$ 与 $c$ 要么通过 $f$ 相连，要么直接与 $c$ 相连。

1. 若 $a$ 与最大点 $c$ 距离更远。

   则同理根据第二个子结论，$a$ 与 $c$ 要么通过 $e$ 相连，要么直接与 $c$ 相连，而此时边 $(a, b)$ 将导致成为环，不成立。

2. 若 $a$ 与最小点 $d$ 距离更远。

   则根据第二个子结论，$a$ 与 $d$ 要么通过 $e$ 相连，要么直接与 $d$ 相连，而根据第一个子结论 $c$ 与 $d$ 有连边，此时边 $(a, b)$ 将导致成为环，不成立。

综上，第二个结论成立。

剩下就是按结论连边，跑最大生成树了。

L

题意简述

$n$ 点，$m$ 边，每个点有点权（可为负），边权为 $1$，到达点可获得点权，并且在任何点都可以以一定花费传送到图中一个点，求至少获得指定点权时的最小花费。

题目分析

观察到 $n \le 200$ 很小，并且普通的边权为 $1$，可以考虑用邻接矩阵暴力，用邻接矩阵表示到达某个点可以获得的最大点权，而边权转化为初始矩阵乘以多少次基矩阵（基矩阵即是花费一个边权时到达点获得的点权）。

再考虑传送，因为传送的花费不为 $1$，但同样很小（$2 \le d_i \le 100$），考虑将边权抽象成一系列点（就像前缀边思想），第 $i$ 个点的编号为 $n + i$，则让 $n + i$ 向 $n + i + 1$ 连边（获得点权设为 $0$），而为了保证传送花费，若第 $k$ 个点的传送花费为 $d_k$，则让 $n + k - 1$ 向 $k$ 连边（获得点权设为 $a_k$，这样只用增加 $d_max - 1$ 个点即可维护传送信息了。

得到了基矩阵，既可以倍增了，倍增 $k$ 次，代表用了 $2^k$ 的花费，所以求出 $2^{0 \sim 30}$ 次方的矩阵，再利用二进制唯一表示原理，即可获得答案。

值得注意的是倍增需要具有单调性，但如果是负点权，则多走一条边获得的最大点权反而而能更少。而为了保证单调性，可以让 $0$ 向 $0$ 连一条边，这样一开始可以反复走 $0$，最大点权就不会减少了。

M

题意简述

给你一个平面和 $n$ 个 $2 \times 2$ 或 $3 \times 3$ 大小的正方形，正方形都有一个权值，如果有重叠，则这两个正方形可以互相到达。如果是相同大小，则权值为 $S \times (v_i + v_j)$，$S$ 是重叠面积的大小，$v_i$ 和 $v_j$ 是正方形的权值。求初始正方形到达其他正方形的最小花费。

题目分析

一个重要一点就是没有完全重合的正方形，所以说显然一个正方形到达的正方形数量有限（当然，如果有重叠，也可以抽象成一个，但还要单独考虑与初始平台重叠的平台的花费）。

考虑到横坐标很小 $1 \le x \le 1000$，所以可以以横坐标为基准，将平面加入到对应横坐标的 vector 当中去，然后对于每个横坐标 vector 按 $y$ 值大小排序。

遍历每个平面，考虑附近的横坐标（大概就是 $\pm 3$ 左右，看具体实现），然后再按照纵坐标二分附近的点，连边即可。

连完边就简单了，剩下就是跑最短路了。

N

题意简述

网格图，但有斜边，求最小割

题目分析

图是平面图，考虑建立对偶图，即是将最小割转化为了最短路。

此图主要是对偶图的建立，建立方式可以如下：

1. 空网格，可以当作有一从左上到右下的路处理，建立一个从右上到左下的边权为 0 的边

2. 有哨塔，上下左右，斜边都不考虑在对偶图中连边

3. 左上到右下以及右上到左下

   考虑将一个格子的上半部分作为标号较小的点，下半部分作为标号较大的点。如果是在 $x$ 行，$y$ 列的网格中，则可以取 ((x - 1) * m + y) * 2 - 1 作为上面的点，((x - 1) * m + y) * 2 作为下面的点。

   而一个格子左边的点和右边的点需要根据路径的方向不同选择，具体可见以下代码：

   

建图完成，就可以跑最短路了，如果距离无穷大则是无解，有限则输出距离即可。

O

题意简述

给你 $n$ 个点，$m$ 条边的图，图中的一条边代表两个点不能同时选择，询问所有的方案数。

题目分析

考虑到 $m - n \le 10$，相差很小，考虑树的情况，那么就是典型的没有上司的舞会 的树上 DP 问题。而如果只多一条边，则是基环树问题。而多出 $10$ 条边又该怎么解决呢？

显然可以按照基环树的思想，让这些边的一个点来固定状态，然后再树上 DP。但如果是枚举 $10$ 条边的状态，再进行一次 $O(n)$ 的 DP，那么其复杂度显然是无法接受的。

考虑优化：因为每次枚举边的一个点状态，只会最多改变 $20$ 个点状态，其他点的情况不变，如果重新整体 DP，不能充分利用之前的信息。考虑将这些关键点抽象成一个虚树，如果我们能在虚树上 DP 那么问题就能解决了。

考虑如何 DP，因为虚树保留了 LCA 信息，所以虚树上子节点（$v$）到父节点（$u$）传递时，路径上是没有其他关键点的，也就是说如果我们能固定子节点的信息 g[v][1] 和 g[v][0]（代表选择和不选择的方案数），那么就能用这两个来表示出到原树上父节点（$u$）的直接儿子（指 $v$ 方向的直接儿子）的信息，从而能递推出父节点 $u$ 的信息（指系数固定的）。

所以说我们要做的就是处理虚树上用子节点的信息表示父节点（$x$）的儿子信息的系数。不妨令为 f[v][0][0] f[v][0][1] f[v][1][0] f[v][1][1]，分别表示 g[x][0] 用 g[v][0]，g[v][1] 的系数，g[x][1] 用 g[v][0]，g[v][1] 表示的系数。

关键是如何递推系数，考虑对一颗树的 DP 过程：$f[u][0] = \prod\limits_{v}{(f[v][0] + f[v][1])}$ $f[u][1] = \prod\limits_{v}{f[v][0]}$，发现递推 $u$ 信息的过程中还需要所有 $v$ 的信息，而虚树中儿子结点到父结点在原树中的路径上（不包括起点和终点）不可能包含其他关键点，所以说我们还要预处理出这条路径上普通结点的其他普通儿子（指子树中没有关键点）正常 DP 得到的信息来递推系数。如果用 gg 数组表示，那么过程可以为：

递推系数的过程可以表示为：

虚树上 DP 可以表示为：

剩下就是枚举多出的边的一个点的状态，然后虚树 DP 了。

几个坑点：

1. 如果虚树板子有问题，没有处理 1 的情况，会导致 1 向 1 连边，然后死循环，栈溢出，re :(
2. 注意是系数是用于递推得到父亲结点在原树的儿子结点的信息，不是直接得到父亲结点的信息。
3. 注意如何枚举状态，以及边之间互相的影响。

P

题意简述

$n$ 个点，$m$ 条边，求最大匹配数。

题目分析

一般图的最大匹配，学一下带花树算法即可。

主要是形成奇环后除根节点以外任意一点都能向外扩展，将花浓缩为一个点（维护花的信息），对环上点向外扩展找增广路即可。

Q

题意简述

题目分析

首先根据直觉和数据范围可以联想到网络流或者二分图的最大匹配，但如何抽象成这种问题呢？

考虑一个转化，将原图上的行列数和为偶数的位置由黑边白，由白变黑，发现此时喜欢的图形即是一个颜色都相同的一个 $2 \times 2$ 的正方形，那么显然我们可以将每个正方形抽象成两个点，一个代表全黑，一个代表全白。

而如果将冲突作为连边，那么黑点和黑点，白点和白点之间显然是没有边的，即可以转化为一张二分图，而答案即是二分图的最大独立集（没有边，即没有冲突），而最大独立集又可以根据最大匹配求出，所以剩下的问题就是如何建边。

首先对于一个原来就既有白又有黑的点（正方形）对答案没有任何贡献，可以省略。如果对于一个有黑色的点，也就意味着白点可以省略；有白色的点，黑点可以省略。

如果我们令有黑色存在的点（正方形）为一类点，白色存在为二类点，都不存在为三类点。

那么一类点的黑点要跟周围冲突的二类点和三类点的白点连边；二类点的白点要跟周围冲突的一类点和三类点的黑点连边；三类点的白点要跟周围的一类点和三类点的黑点连边，黑点跟周围的二类点和三类点的白点连边，而且自身的白点跟黑点连边。此时就将所有冲突连边连接完成。

剩下即是用网络流跑二分图最大匹配了，可以虚拟一个源点向所有白点连边，虚拟一个汇点被所有黑点连边。边的容量都为 $1$，剩下就是跑最大流了。

R

题意简述

给你一个平面，平面上的 $n$ 个点的 $(x_i, y_i)$ 信息， 两个点之间的距离为 $\min(\left|x_A - x_B\right|, \left|y_A - y_B\right|)$，询问从起点到终点的最短路径。

题目分析

如果是 $\max$ 那么就是切比雪夫距离，两点间的最短距离显然就是一点直接到另一个点。可这里是 $\min$，考虑如果直接连边，那么会连 $n^2$ 条边，其空间和时间复杂度都是不可接受的。

考虑如何优化建边，如果一个点（假设 $(x_1, y_1)$）想通过 $x$ 方向到达另一个点（假设 $(x_2, y_2)$），那么显然我们可以将 $x$ 坐标位于两者之间的点作为中介，因为最差的结果都是通过两次 $x$ 方向移动来到达另一个点，如果有一次从 $y$ 方向移动，那么就意味着答案比一次从 $x_1$ 到达 $x_2$ 的花费更小（因为是取 $\min$，所以这启示我们按照 $x$ 大小，排序，相邻点之间连边即可。而 $y$ 方向同理。

建边之后跑最短路即可。

S

题意简述

$n$ 个点，$m$ 条边，$k$ 次操作，每次操作能使边权由 $\dfrac{1}{a}$ 变为 $\dfrac{1}{a + 1}$，初始边的 $a$ 都为 1。给你两条路径 $s_0 \sim t_0$ 和 $s_1 \sim t_1$，请问两条路径之和最少为多少。

题目分析

注意到 $n \le 5000$ 不是特别大，且初始边权为 1。最终形成的边可以分成两个集合，一个集合是经过两次的，一个集合是经过一次的。显然经过两次的边是一条链，否则如果有形成两条链，则让两条路都经过连接两条链最少的一条路径更优。所以可以考虑枚举经过两次的始末点。

先预处理出两两点之间的距离最小值（BFS）。然后枚举始末点，考虑到我们并不关心具体路径，所以可以只考虑其贡献，取相同经过两次的路径长度中的经过一次路径长度的最小值，令为 minx[x]（代表经过两次的路径长度为 x 的情况下，经过一次路径长度的最小值）。

注意到对于一些边，对这些边平摊操作是最优的，所以对于 $a$ 条边，$b$ 次操作的答案为：

以 $b$ 为自变量，可以发现此时是多项式和分式的乘积，猜测是一个单峰函数，可以用三分，得到最值。

所以剩下即是枚举对经过两次的边使用多少次操作，再用 calc 函数计算两次边和一次边的贡献进行三分即可得到答案。

注意考虑一些点不连通情况，题目没说，也不知道卡没卡，但如果起点和终点都不连通就无解了（

T

题意简述

给你一张 $n$ 个点，$n - 1$ 条边的连通有向图，将点分为三类，一类为入度为零的点，作为起点；一类为出度为零的点，作为终点；剩下点为第三类。求任一起点到任意终点必经的第三类点。

题目分析

我们可以从方案数出发，原图求出起点到某一点的方案数（令为 f），反图求出终点到某一点的方案数（令为 g），总方案数即为 $\sum\limits_{t}f[t]$ 或者 $\sum\limits_{s}g[s]$，不妨令为 $x$，如果某一点 $u$ 满足 $f[u] \times g[u] = x$，那么显然这点即是必经点。

所以说剩下的过程就是求 f 和 g 了。

显然可以通过按拓扑序来求，求完后遍历点判断即可。

V

题意简述

给你一张 $n$ 个点，$m$ 条边的有向图，且每个点的入度最多为 $1$，求弱连通分量数量。

题目分析

首先求弱连通分量数量，显然可以先 tarjan 缩点，将强连通分量缩成一个点而不影响答案。然后注意到每个点的入度最多为 $1$，那就是意味着最终的图形是由一条条链组成的图形，而不会是各种奇怪的图形。

而对于一条条链组成的图形的弱连通分量数是很好统计的，显然就是出度为 $0$ 的点的个数。

所以这题就是 tarjan 缩点，然后求出度为 $0$ 的点数有多少个。

W

题意简述

给你一个 $n$ 个点，$m$ 条边的二分图，求最小点覆盖。

题目分析

按照 König 定义，二分图的最小点覆盖等于最大匹配数。所以在二分图中求最大匹配即可。

二分图的最大匹配算法可以用匈牙利算法不断求增广路即可。

X

题意简述

给你一个 $n$ 个点，$m$ 条边的有向图，对于任意一条从 $1$ 到 $n$ 的路径，你只能删除 1 条边，问是否存在一种方案使最后无 $1$ 到 $n$ 的路径。

题目分析

发现如果没有删边限制，那么其实就是最小割问题。现在问题是如何魔改最小割使跑最大流时不多删除边。

普通跑上图的最大流是 2，但也意味着删除了 $<3, 5>$ 和 $<2, 4>$ 边，也意味着一条 $1$ 到 $n$ 的路径删去了两条边。

如何让跑最大流时让 $<2, 4>$ 成为割边（一条最大流路径上流量最小的边）而不让 $<3, 5>$ 成为割边（不是一条最大流路径上流量最小的边）呢？

先思考会出现删除一条路径上两条边的出现条件：

两条最小割的边 $<u_1, v_1>$ 和 $<u_2, v_2>$，且存在一条路径 $v_1 \rightarrow u_2$。

那么如果我们在 $v_1 \rightarrow u_2$ 路径上反向建无穷大流量的边，会有什么效果呢？发现 $<u_1 ,v_1>$ 不再成为割边，因为从 $u2$ 到 $v1$ 可以有更大的流量通过，$<3, 5>$ 将不再限制 $<5, 6>$。

所以在原图上建立无穷大容量的反向边即可。

可以发现，建立反向无穷流量的边产生的影响还有使原来不能到达的点能到达了，所以需要提前预处理将这些点排除。

同时要注意无解的情况，不管怎么删都会删除至少两条边，那么意味着有一条路径从 $1$ 到 $n$ 的路径可以重复经过路径上的所有边，也就是说 $1$ 到 $n$ 的路径形成一个环，即 $1$ 和 $n$ 在同一个强连通分量的情况下。发现此种情况下的最小割也是无穷大的，所以说也可以用最小割来判断。

Y

题意简述

题目分析

考虑一颗树的情况，那么就是 dsu on tree 的例题，但是若用树状数组修改询问，那么复杂度 $O(n\log^2n)$。

可是这不是一棵树，而且比树多了很多边。那么我们考虑边的影响。

因为是删去到 $1$ 的路径，那么我们以 $1$ 为根节点，那么对于树，那么其实就是统计子树信息。而若如下图，多出了一条 $(3, 6)$ 边：

那么显然只会对 $2$，$4$ 结点的答案统计有影响，即不能再统计此方向的子树。

总结一下，多出的边会对原树上路径上的点除了 LCA 和两边端点产生影响。

如果我们在 dfs 的过程随意建一颗树，那么这个非树边在原树只会是一条从儿子结点到祖先结点的一条链，也就是说只会对两端结点产生影响（LCA 即是一个端点）。所以说我们很容易在 dfs 的过程中，找出非树边多出的链上的结点（用栈就很容易求出来），然后给这些结点打个标记，代表不对父亲产生贡献（具体打上标记的结点是除去链顶端两个结点），然后剩下就是魔改 dsu on tree，增加判断是否保留，然后记得如果当前是保留还要增加没有统计的点。可以发现复杂度还是没变的，仍是 $n\log^2n$。

Z

题意简述

$n$ 个点，$m$ 条边，判断任意 $n$ 个点，$m - 1$ 条边的树是否两两同构。

题目分析

边数为 $m - 1$ 时显然成立。

边数为 $m$ 时，即是奇环树，为了形成树，显然只能拆环上的边。所以可以 dfs 一下得到环上的点，然后对环上的点向环外形成的树进行树哈希。如果将环看成一条链，将其树哈希的值作为一个数列。那么如果要满足题意，要么数列所有值相同，要么数列个数为偶数个且值是交替出现的。

其中树哈希的方式可以是 $h(a) = 1 + \sum\limits_{v}f(v)$，f 是哈希函数，哈希函数可以为

而边数大于 $m$ 时，手模一下可以发现大抵是不行的（