1、dfs树

在这里插入图片描述

在这里插入图片描述

（一）无向图

对于一个无向图，若其连通，那么在经过dfs后，被访问的边数为n-1条，称为树边，剩余的边称为回边。

结论1：回边必然连接了一个结点与其祖先。

结论2：树边 uv 是桥当且仅当此时没有回边跨越它，回边一定不是桥。

找桥算法可以由传统的low[u]实现。我们也可以——用 dp[u] 来定义跨越点 u 和他的父节点的回边的数量。然后：
$dp[u] = (从u点开始的向上的回边) - (从u点开始向下的回边) + \sum dp[v] $，v是u的子节点.当且仅当dp[u] = 0时连接u及其父节点的边是桥。

结论3：给所有的边定向，生成有向图。如果原图有桥存在，那么新图不可能强连通（如果uv是桥且我们将其定向为 u → v，那么现在就不存在由v到u的边）。如果原图无桥（也就是任意树边都被至少一条回边跨过），那么使树边向下、回边向上，则****任意节点都可以回到根节点****，从而新图必然强连通。

结论4：回边u-v的两端构成了一个环，环的大小为deep[u]-deep[v]+1。任何环至少包含一条回边，因此可以利用此性质处理边双连通分量。对于包含超过两条回边的环，需要更复杂的做法，

（二）有向图

在有向图的dfs中，不一定能遍历所有的点。现在假设所有点都能被访问到，那么除了树边外，其他的边分为两类：连接了子孙节点和祖先节点的边为****回边*，且有上下方向之分；其余的边为横跨边，*横跨边一定是由后访问的结点指向先访问的结点，它连接了两个兄弟结点或兄弟子树。有向型的 DFS 树被用来构造有向图的支配树。

沿根方向的回边被称为向前边或返祖边，沿叶子方向的回边被称为向后边。有向图的dfs树性质复杂，依题境而异，以下提供一些特殊情况：

1 若只有返祖边，不存在横向边和向后边，那么根节点到任意节点的初级路径（点不重复）只有一条。

（三）特殊图

二分图：考虑用黑白二色给一幅无向图染色，如果可行，那它就是二分图。在dfs树中，令树边连接不同颜色的点，并将连接了相同颜色的回边称为矛盾边。

如果将一条树边删除，然后将独立出来的子树翻转颜色，那么矛盾边就变成了非矛盾边，非矛盾边就变成了矛盾边。所以，我们动态规划找到所有只被矛盾边跨越的树边，删除它们，得到的就是二分图。

仙人掌图

(https://files-[cdn](https://so.csdn.net/so/search?q=cdn&spm=1001.2101.3001.7020).cnblogs.com/files/ambition/cactus_solution.pdf)

基本定义：1强连通、2每条边最多属于一个环

（1）无向仙人掌图：

2.jpg

对于无向仙人掌图，dfs满足任意树边最多只被一条回边跨越。简单的判断方式：找到一条向下返祖边时，从返祖边的下端向上追溯，对每个节点的父边权值+1，如果某个边权的值大于1，则整个图并非仙人掌图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for(int i:G[x])
{
    if(!dfn[i])
        dfs(i,x);
    else if(dfn[i]>dfn[x]) //此方向是一条向下返祖边
    {
        int y=i;
        while(y!=x)
        {
            if(tag[y])
            {
                cout<<"0";exit(0);
            }
            tag[y]+=1;
            y=fa[y];
        }
    }
}

我们可以借助仙人掌图在dfs树中的性质来简单地缩点——

1.给每个回边一个从 N + 1 开始的唯一的编号。
2.对每一个点u，统计跨越u的回边的编号，记为cycleId[u]；如果u不在一个环里，则标记cycleId[u] = u。
3.建立一个新的连接表，对每一个u，用cycleId[u]将其代替。

（2）有向仙人掌图：（也要满足整幅图的强连通）

imgimg

有三个性质可以唯一判断有向仙人掌图。

性质 1 仙人掌图的 DFS 树没有横向边。

性质 2 Low(u)<=DFN(v) (u 是 v 的儿子) 。（强连通图无桥）

性质 3 设某个点v有a(v)个儿子的Low值小于DFN(v)，同时v自己有b(v)条向上边。那么a(v)+b(v)<2。（否则必会出现一条边被多个圈包含）

2、dfs序

（一）欧拉序

1
2
3
4
5
6
7
8
9
10
void dfs(int x,int f)
{
	in[x]=++tim;
	for(int i:G[x])
	{
		if(i!=f)
			dfs(i,x);
	}
	out[x]=++tim;
}

搜索到每个节点时，前后记录一次时间戳，得到一个长度为2N的序列，每个编号出现两次，记第一次的时间戳为in[x]，最后一次的时间戳为out[x]，则int[x]与out[x]的中间部分为x的子树。

性质1：如果x被in[y]和out[y]包含，那么y是x的祖先。

性质2：:时间序中，任意子树都是连续的，且符合括号匹配，也就是只会出现([()]){}的形式，不可能出现[(])。

性质3：对于任意路径a-b，若：

1 lca(a,b)为a或b，则a-b为in[a]到in[b]的奇数次元素（或者out[b]到out[a]，根据它们的大小排先后）。

2 lca(a,b)不为a或b，则a-b为in[a]到out[b]（或in[b]到out[a]）的奇数次元素加上lca(a,b)。

利用上述性质可以实现一些树上操作：

1 单点修改，子树求和：

前缀和处理时间序（可用树状数组），如果对out[x]加w（当然in[x]也可以），那么所有包含x的区间也都加w，****这就相当于对其所有祖先+w****，那么在查询以结点y为根的子树权值和时，就可以由sum(out[y])-sum(in[y]-1)得出。将前缀和换为差分，就可以做到子树赋值、单点查询，具体就是in[y]+w，(out[y]-1)-w，查询点x时之间求sum(x)即可。

2 路径修改，单点查询：

差分处理时间序，如果想对某一路径x-y赋值，那么只需$out[x]+w，out[y]+w，out[lca(x,y)]-w，out[fa[lca(x,y)]]-w$。查询点权时，相当于累和其子树，即求$sum(out[x])-sum(in[x]-1)$。

树上莫队

欧拉序的大部分功能都可以由接下来的dfs序所实现，欧拉序比较有优势的领域是树上莫队（Mo’s Algorithm on Trees Tutorial] - Codeforces）

以查询路径上不同点权为例，在in[x]作标记val[x]，表示x的点权+1，在out[x]作标记-val[x]，表示x的点权-1。假设要查询的路径为x-y，$lc=lca(x,y)$，假设$in[x]<in[y]$，那么：

Case 1：x==lc。所对应的查询区间为$[in[x],in[y]]$。

Case 2：x!=lc。所对应的查询区间为$[out[x],in[y]]+{in[lc]}$。

路径维护（尚未完全理解此做法

我们将欧拉序建立为括号序，即，第一次出现x的位置为”(“，最后一次出现x的位置为”)”。我们先从简单情况出发，假设边权均为1，对于树上路径x-y，假设$in[x]<in[y]$，我们截取$[in[x]+1,in[y]]$这部分，比如”() ) ) ( ( ) ) ( (“，我们删去匹配的括号，发现还剩余4个括号，这表示x-y的路径长度为4。（由于是处理路径上的边权问题，我们无需像前文一样额外地考虑LCA。）

一般地，假设两个节点P和Q，如果介于P和Q之间的非匹配括号数量为(a,b)，表示有a个左括号和b个右括号（具体形态是左边连续a个”)”+右边连续b个”(“ ），则P和Q在树上的距离就是a+b。

设$x-y$为链$s1(a,b)$，$y-z$为链$s2(c,d)$。注意到s1和s2合并起来时会产生min(b,c)的匹配括号，则合并后的路径长度为$s1+s2=a+d+|b-c|$。

将所有节点按dfs序排列，我们可以预处理出相邻节点的二元组，接着建立线段树，就可以合并得到任意两点的路径信息，从而维护一些特殊的路径。我们一般用此线段树来维护全局的某些特殊路径信息。

更详细的讲解：[ZJOI2007]Hide 捉迷藏——线段树+括号序列博客园

然后考虑一个典型题 CF1192B]动态直径 - GreenDuck - 博客园 (cnblogs.com)

（二）dfs序

1
2
3
4
5
6
7
8
9
10
void dfs(int x,int f)
{
	l[x]=++tim;
	for(int i:G[x])
	{
		if(i!=f)
			dfs(i,x);
	}
	r[x]=tim;
}

基本性质：任意节点的dfs序都是序列中的连续部分，一颗子树的所有节点在DFS序内是连续的一段。dfs序就是所有结点的访问顺序，其长度为N，相当于没有out部分的欧拉序。记l[x]为x子树的开始位置，r[x]为结束位置。（或者以dfn[x]记录x的时间戳，用sz[x]记录x的子树大小，即x子树在序列中的长度）。

虽然看似是欧拉序的简化，却省去了欧拉序中不必要的out部分，能实现欧拉序的基本功能：

①单点修改，子树求和。

②路径修改，单点查询。

原理同上，不再赘述。

dfs序把子树变成了连续序列，也就是说，维护任意子树可以转变为维护某段序列，这启示我们可以尝试把树上问题引申为对子树的赋值与查询。赋值时均对l[x]进行操作。

③单点修改，路径求和。

路径查询问题普遍可以转换为查询点到根距离问题，而当一个点被赋值(+w)时，只有它的子树中的结点到根距离受影响，即全体+w。于是转换问题为子树修改，单点查询问题（做法见欧拉序，原理就是普通的区间修改和单点查询）。

④路径修改，子树求和。

路径修改同上，依旧应用差分实现。对于结点y的子树下任意结点x，考虑其差分v[x]在y上的贡献：$v[x](deep[x]−deep[y]+1)=v[x](deep[x]+1)−v[x]deep[y]$。深度之差表示x到y包含几个结点。于是节点y的子树和为：$\sum_{i=l[y]}^{r[y]}v[i](deep[i]+1)-deep[y]\sum_{i=l[y]}^{r[y]}v[i]$。很容易想到再开两个树状数组维护。

⑤子树赋值，路径查询。

当一棵子树被整体赋值时，只有其下结点到根的距离受影响，对于结点y的子树下任意结点x，若子树被赋值w，则x的增量为$w*(deep[x]-deep[y]+1)=w(deep[x]+1)−wdeep[y]$，采用两个树状数组进行该区间赋值，一个赋值w（待单点查询时再(deep[x]+1)），一个赋值$w * deep[y]$。

模板题：https://loj.ac/p/146

ps:当需要同时实现多种修改功能时，仍需要树链剖分

——dfs序的其他重要性质与功能：

① 取一个点为根，从根出发对其子树dfs，那么在这个过程中，子树中的每条边显然被经过2次。于是，在dfs序中该子树所在区间内，累和相邻节点的树上距离，额外加上左端点和端点的距离，所得结果就是这棵子树边权之和的两倍。

从dfs序中择取若干点，按原序排列，累和相邻节点的树上距离，额外加上左端点和端点的距离，所得结果就是恰好连通这些点的子图的边权之和的两倍，该子图也是一棵树。

对这类性质做个总结：对于若干点在树上围成的连通子图，将这些点按dfs序排列，且首末相接，那么相邻两点的路径，恰好能将整个子图覆盖两次。

②将“路径赋值”进一步延伸为：将树链x-y上某种元素的数量+k，并在最后给出一系列询问，查询节点x中z元素的数量。我们第一时间想到权值线段树合并，不过这种方式统计的是一个节点中所有元素各自的数量，不仅空间庞大，对于我们只想查询一个元素的信息来说也显得多余了些。

在dfs序中，查询节点x中z元素的数量（一个点可储存多种元素），无非就是累和x子树内有关z的差分。每个x节点有一个vector，储存z的差分（每次赋值最多只产生4个差分，总空间是足够的）。我们开一个全局数组c，c[z]表示z当前的差分之和，然后从左到右遍历dfs序，维护数组c。对一个节点x，若待查询z的数量，则在到达l[x]时记录c[z]的值last，在到达r[x]时，c[z]-last（必非负）就是此区间中z差分的累和。

对这类性质做个总结：从根出发，维护一张信息表，如果树边向下对应着某个操作（这个操作也可以像差分一样对应在点上），那么在第一次到达某个点时，我们就能得到这个点经过操作后的状态，也就是当前的信息表；如果树边向上对应着某个操作，那么我们要在第二次（也就是回溯）到该点才能得到它的状态。无论哪种情况，前后两次到达一点，点的状态的变化就对应了所有加在它上面的操作。

由于树本身的性质，一般是采取向上边居多，比如树上差分就是采取向上边，且叶子作为（多个）信息表起点，在相遇时多表合一。而对于向下边，则以根为表的记录起点，通常需要将信息表初始化为根节点的状态（常见的问题模型为：某个结构（比如图）由之前的结构通过某些操作生成而来）。在完成信息处理后，我们就要把动态表在具体节点的当前状态保存在该节点上。为这张表可以是一个变量，一个数组，一个数据结构，甚至是一个数组的哈希值，这取决于节点的状态需要如何保存。了保证回溯到某个节点时，表的信息一致，需要在回溯时采取与向下边逆反的操作。

（三）欧拉环游序

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x,int f)
{
	in[x]=++tim;
	for(int i:G[x])
	{
		if(i!=f)
        {
            dfs(i,x);
            out[x]=++tim;
        }
	}
}

树上任意两点x和y，两点的lca，为第一次出现x和第一次出现y区间内，时间戳最小的那个值。即$sa[ min( dfn(x)到dfn(y) ) ]$
结合st表，可以在O(1)求出lca，适用于频繁求lca的场景。不过所需空间为2nlong2n，当数据量接近百万时可能会吃不消（>256MB）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//O(1)求LCA——欧拉环游序+ST表
int dfn[maxn],sa[2*maxn],st[22][maxn*2],bin[32],tim;
void dfs(int x,int f,int d)
{
	sa[++tim]=x; //生成欧拉环游序
	dfn[x]=tim; //时间戳（每个节点在欧拉环游序中第一次出现的位置）
	int n=G[x].size();
	for(auto p:G[x])
	{
        int i=p.first;
		if(i!=f)
		{
			dfs(i,x,d+p.second);
			sa[++tim]=x;
		}
	}
}
void init()
{
	bin[0]=1;
	for(int i=1;i<30;++i)
		bin[i]=bin[i-1]*2;
	for(int i=1;i<=cnt;++i)
		st[0][i]=dfn[sa[i]];
	for(int i=1;i<=22;++i)
	{
		for(int j=0;j+bin[i]<=cnt;++j)
		{
			st[i][j]=min(st[i-1][j],st[i-1][j+bin[i-1]]);
		}
	}
}
inline int lca(int x,int y)
{
	int a=dfn[x],b=dfn[y];
	if(a>b)
		swap(a,b);
	int t=log2(b-a+1);
	return sa[min(st[t][a],st[t][b-bin[t]+1])];
}

3、生成树

（一）最小生成树

基本性质总结：（详见博客）

1） 定义在一棵树里添加一条边，并在产生的圈里删除一条边叫做一次操作。（也就是说换掉一条边并且保证结果是树），则树A和B是无向图的两个生成树，则A可以通过若干次操作变成B。

“可以通过若干次操作”，这个“可以”并没有“特殊”的含义，也就是说我们可以随便加一条B有而A没有的边，总可以找到一条合适的边删掉。

（2） 把一个连通无向图的生成树边按权值递增排序，称排好序的边权列表为有序边权列表，则任意两棵最小生成树的有序边权列表是相同的。（算法导论23.1-8）

注：这个命题说明，如果无向图的边权都不相同，则最小生成树是唯一的。但是其逆命题不成立。即如果无向图的最小生成树唯一，则无向图的边权是可能有相同的。例子，比如原图本身就是一棵树，并且有两条边的边权相等。

（3） A,B是同一个无向连通图的两棵不同的最小生成树，则A可以通过若干次（1）中定义的换边操作，并且保证每次结果仍然是最小生成树，最终转换成B。

（4） 一个连通无向图G,不会有一棵最小生成树包含G的一个圈中全部最大权值的边。

注：特别地，如果一个圈中权值最大的边唯一，则最小生成树不包含这条边。

至此证明了任何两棵不同的最小生成树A,B，可以随意选一条B有而A没有的边，添加到A上，由（4）的结论，形成的圈里，至少有一条边和这条新加的边权值相同（正是这些环中权值相同的边形成了不同方案），并且它不在B中，删掉它。这样可以最终把A转化成B。

（5） 对于一个连通无向图的生成树，只考虑它的边权，形成的有序边权列表中，最小生成树是有序边权列表字典序最小的。

注：有了（2）的结论，结合Krusal算法的过程，知道Krusal算法加边的顺序构成的边权列表就是一个有序边权列表。于是，只考虑有序边权列表时，可以用Krusal算法产生的特殊的最小生成树代替任何一棵最小生成树。

（6） 一棵树不是最小生成树，则一定存在一个（1）中描述的操作，使得操作之后，它的总权值减小。

对生成树上的节点s对其他任一节点x，若s与x存在权值为w的非树边s-x，且在s到x的树上路径中存在树边e的权值比w大，那么可以断开e并连接s-x，使得生成树的总权值减小。不妨令e为s到x的路径上权值最大的边，那么先可以以s为根跑dfs预处理，设dp[x]为x到根的路径的最大边：$dp[x]=max(dp[fa[x]] , w[x到fa[x]])$，再遍历s-x，就可以在固定s的情况下O(n)完成一次（6）。若s不固定，我们也可以用树上倍增（或者树链剖分）的方法，直接查询一段树链中的最大边权。

（7） 一棵生成树不是最小生成树，则一定存在（1）中的操作，不断进行把它转换成一棵最小生成树，而且每次操作后权树的总权值都会减小。

注：由此可知，这种操作也是“任意”选边的，并没有特殊性。如果把一个图的所有生成树看作节点，把对每个生成树进行一次（1）中定义操作看作形成的树作为它的邻居。

那么综合上述结论：形成的图是个无向连通图。任何“局部最优解”也是“全局最优解”(只进行一次操作不能减小总权值，则是最小生成树，可以随意从任何一个“非最优点”，保持权值减小地逐步达到“最优点“)。

（8） 如果一棵生成树，任何边都在某棵最小生成树上，则它不一定是最小生成树。

反例：考虑一个长为2，宽为1的矩形。构造一个无向图，节点就是矩形顶点，边就是矩形的边，边权就是矩形边长。显然，原图有两棵最小生成树（“两宽与一长”），所有边都在某棵最小生成树上，但是有两棵生成树不是最小生成树（“两长与一宽”）。

总结完性质，那么，什么边可以作为最小生成树的树边呢？

对已经生成的最小生成树，树上两点存在唯一路径，如果想修改一条非树边i-j的权值使其成为树边，那么考虑：加入i-j后，有环出现，必须删掉环上另一条边才能维持树结构，显然我们应该应该找权值最大的一条，从而得出结论：

（1）对于一条不在最小生成树上的边，令其权值小于等于这条边两端点在树上的路径中边权最大的那条边的权值，则可跻身最小生成树中。

如果该路径上的树边权值都比所新加的这条边要小，那么这条边就无法加入，即：

（2）对于一条处在最小生成树上的边，必须满足其权值小于等于所有跨过它的非树边（横跨边、回边）。

如果对每个树边去寻找跨越自己的非树边，以找到权值上限，这显然不现实，我们可以枚举每个非树边，更新其跨越的区域的min。

（3）断开任一树边e，则将点集分成了两个连通分量（两棵树），那么使e成为树边的必要条件是：在所有直接连接这两个连通分量的边中，e的权值最小。

我们回顾一下Kruscal算法。在Kruscal算法的过程中，将树边从小到大连接（反过来就是从大到小断开），每加一条边，就是将两个连通分量合并起来（其信息用并查集维护，出边信息可借助bitset记录），该边作为树边的必要条件是该边权值在所有连接这两个连通分量的边（暂称边集E）中最小，对于每条待加入的边，其E不重叠。由上，Kruscal算法可以看做一种总开销最小的连通块（并查集）合并过程。

其他重要性质——

（4）最小生成树的子树，在其连通块内仍然是最小生成树，所有的局部最小生成树组成图的最小生成树。

算法实现：

Prim的复杂度为O(nm)，在稠密图中比Kruskal优，在稀疏图中比Kruskal劣（Kruskal需要对边排序，其复杂度为mlogm）。Prim+Heap可以达到O(mlogn)，当然代码量要更大一些。

（二）Kruskal重构树

瓶颈生成树

无向图G的瓶颈生成树是这样的一个生成树，它的最大的边权值在G的所有生成树中最小。 ——OI-wiki

根据最小生成树定义，x 到 y 的最小瓶颈路上的最大边权等于最小生成树上 x 到 y 路径上的最大边权。虽然最小生成树不唯一，但是每种最小生成树 x 到 y 路径的最大边权相同且为最小值。也就是说，每种最小生成树上的 x 到 y 的路径均为最小瓶颈路。

但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 x 到 y 的简单路径。概括地讲，最小生成树是最小瓶颈路的充分不必要条件。我们寻找两点间的瓶颈时，等价于在最小生成树上查询两点路径中的最大值（若找所有路径的最小边权最大值，则等价于在最大生成树上查询两点路径中的最小值）。

Kruskal重构树

在跑 Kruskal 的过程中我们会从小到大加入若干条边，现在我们仍然按照这个顺序。

Kruskal是合并集合的过程，每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将所链接的两个集合分别设为新建点的左儿子和右儿子，然后我们将两个集合和新建点合并成一个集合，将新建点作为根。

不难发现，在进行 n-1 轮之后我们得到了一棵恰有 2n-1（其中有 n 个叶子）的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。

img左图的重构树为：img

重构树无边权，有点权，每个非叶子结点都一一对应着最小生成树上的一条边。它具备一些比较优良的性质，因此能方便地解决一些问题。（以下默认为最小生成树的重构树，基于最大生成树的重构树性质不再赘述）

  • 重构树上两个叶子结点 x 和 y 之间的路径上的点（不包含 x 和 y 本身）与最小生成树上 x 到 y 的路径上的边一一对应。
  • 在重构树里，深度越浅的结点的权值一定越大。（重构树是一个二叉堆）

这其实就是 kruskal 重构树算法的精髓和妙处所在。由于我们在进行 kruskal 算法时是按边权从小到大选的，因此边权大的边一定更晚被选中，转换到重构树上就是深度更浅。这样一来，重构树上的结点的深度就与重构树上的点权、最小生成树上的边权联系在了一起。

  • 最小生成树上任意两点 x , y 之间的“瓶颈”的大小与重构树上 x , y 两点的最近公共祖先（lca）的点权相同。进一步地，原图上任意两点 x , y 之间的最小“瓶颈”的大小与重构树上这两点的 lca 的点权相同。
  • 对于图上一点 x ，满足与 x 的最小瓶颈的大小 ≤ val 的所有点在重构树上是同一结点的子树里的所有叶子结点。

如果 y 是重构树上 x 到根结点的路径上权值最大的满足权值 ≤ val 的结点（也就是最浅的满足条件的点），x 肯定属于 y 子树内的叶结点，而对于其他节点 z ，只有当 lca(x,z) 也在 y 子树下，路径x-z 才能满足条件，也就是说 z 必然在y子树下。

对于权值为w的（非叶）节点 k ，其不同儿子子树下的节点，两点之间的路径瓶颈即为 w ，也就是说我们可以在 k 上来统计这样的点对。

最小生成树上的边，就是在确保最大边权尽量小的情况下，任意两点会选择走的边（即便不唯一）。如果封锁途中边权大于 val 的无向边，然后以某一点 x 为起点，寻找可到达的点。对于这些点，我们找到 x 的祖先中权值不大于 val 的最大者，那么 x 即可到达该祖先子树下的全部叶子节点。考虑到将叶子（原图的点）按dfs序排列后，这些x可到达的的点是连续的，因此可转换为序列问题，问题就好处理多了。

img

（三）最小树形图

有向图的“最小生成树”叫做最小树形图，是有一棵不存在有向环的有向树，除了根结点u外的每个顶点都只有一条入边，而最小树形图则是总权值最小的那棵。

image-20210817184328177

在这里插入图片描述

（如图2，无法用用prim或krustra算法来解决，因为有向图不能利用连通块合并的思想）

算法步骤：首先找到除根外每一个点的最小入边（共n-1条，不包括自环），构成边集E。如果除根外某个点没有入边，那么一定没有树形图。

理想情况下，仅凭这些边（前驱）就将所有点连成了一棵树，这就是所求的解。如果不是树，那么这些边形成了什么图形呢？

由于只有n-1条边，如果不成树，那么整个图将分成若干个块，其中含根节点的块必为树结构，其他块为“水母”结构（包含一个一元环，并向外延伸若干“触手”）。

image-20220707144605652

想要把块合并到一起，就必须断开水母头上的某条边（其他的边可以直接保留至最终结果），也就是更换环上某点的前驱。考虑v是水母头上一点，a是当前前驱（环上的边），e是v的任一其他入边，如果我们断开a连接e，那么总权值的变化为w[e]-w[a]。一般来说，我们只考虑最终结果的总权值，不需要真正地物理删除a，因此我们把所有e的权值减去w[a]，这样当e被选择时，a的贡献就消失了。

判断一个点是否在环上？首先，如果沿着前驱能找到根，那一定不在环上；若陷入循环（设一个计数器），却又回不到自己，说明点在触手上；否则，点必在一个环上。可以观察每个点最后是因为什么退出循环的。如果所有点都没有检测到在环上，则统计结果输出。

如果存在有向环的话，我们就要将这个有向环所称一个人工顶点new（开新点，或者从环上找一代表点），同时改变图中边的权。假设某点u在该环上，并设这个环中u的前驱边权是in[u]，那么对于每条从u出发的边(u, i, w)，在新图中连接(new, i, w)的边；对于每条进入u的边(i, u, w)，在新图中建立边(i, new, w-in[u])的边。如果新点new没有入度，树边不存在。

接下来描述缩点操作：选出任意代表点t，环上的其他点打上tag，在今后的一切循环中忽略。t要继承所有环点的边关系（原图中的），对环上的点v、环外一点k，无论有多个v指向k还是k指向多个v，显然t只需继承最小的一条。环上所有的边权计入ans。

某一刻，当发现找不到环时，将所有点（当然了，不包括被打tag的）的前驱权值计入
ans，即为结果。下为朱刘算法，O（VE）。算法顺序：扫描前驱——搜索有向环——标记环——缩点（集中边）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void init()//不能少了初始化的内容
{
    memset(vis, 0, sizeof(vis));
    memset(flag, 0, sizeof(flag));
    for(int i=0; i<=n; i++)
    {
        w[i][i] = INF;
        for(int j=i+1; j<=n; j++)
            w[i][j]=w[j][i]=INF;
    }
}
 
double directed_mst(int u)//u表示根节点
{
    double ans=0;
    memset(vis, 0, sizeof(vis));
    while(true)
    {
        //求最短弧集合E
        for(int i=1; i<=n; i++)if(i!=u&&!flag[i])
        {
            w[i][i]=INF, pre[i] = i;
            for(int j=1; j<=n; j++)
                if(!flag[j] && w[j][i]<w[pre[i]][i])
                {
                    pre[i] = j;
                }
            if(pre[i]==i)return -1;//也可以用dfs预处理判断凸的连通
        }
        //判断E是否有环
        int i;
        for(i=1; i<=n; i++)
        {
            if(i!=u&&!flag[i])
            {
                int j=i, cnt=0;
                while(j!=u && pre[j]!=i && cnt<=n) j=pre[j], ++cnt;
                if(j==u || cnt>n) continue; //最后能找到起点（根）或者是走过的点已经超过了n个，表示没有有向环
                break;
            }
        }
        if(i>n)
        {
            for(int i=1; i<=n; i++)
                if(i!=u && !flag[i]) ans+=w[pre[i]][i];
            return ans;
        }
        //有环，进行收缩，把整个环都收缩到一个点i上。
        int j=i;
        memset(vis, 0, sizeof(vis));
        do
        {
            ans += w[pre[j]][j];
            j=pre[j];
            vis[j]=flag[j]=true;//对环内的点标记，并且直接对环的权值进行加和记录，在最后找到最小树形图之后就不用展开收缩点了
        }
        while(j!=i);
        flag[i] = false; // 环缩成了点i，点i仍然存在

        //收缩点的同时，对边权值进行改变
        for(int k=1; k<=n; ++k)if(vis[k])  // 在环中点点
        {
            for(int j=1; j<=n; j++)if(!vis[j])   // 不在环中的点
            {
                if(w[i][j] > w[k][j]) w[i][j] = w[k][j];
                if(w[j][k]<INF && w[j][k] - w[pre[k]][k] < w[j][i])
                    w[j][i] = w[j][k] - w[pre[k]][k];
            }
        }
    }
    return ans;
}

（四）矩阵树定理

4、树上问题

（一）树的直径

树的直径：树上最长的链，亦指这条链的长度。

性质（边权非负）：

1 设树T存在直径a1b1，a2b2……an~bn，从树上任意点c搜索最远点，可能有多个最远点，它们与c的距离一定相同，且任取一最远点，一定是某条直径的端点，因此最长距离$d = max(dis(c, a1), dis(c, b1)) = max(dis(c, a2), dis(c, b2)) = … = max(dis(c, an), dis(c, bn))$。

**推论：以某直径端点a搜索最远点，可能有多个最远点，且a与这些最远点距离都为树上最大距离，即a与它们都能组成直径。 **

举例：边权为1的树上，求任意一个与x距离恰为k的点编号（保证存在）。我们只需要找到一条直径，以其两端点为根建两棵有根树，就一定能保证x的k级祖先存在。

2 给定一棵树，对于它的任一直径，若取其几何意义上的中点，叫做这条直径的中点。那么， 一棵树的所有直径的中点必定是同一点。

直径/2的位置可能是一个点，也可能是某条边（也就是这条边所连接的两点被所有直径经过，可以缩为一点处理），任取一条路径便可求出。如果恰好是一个点，那么它同时也是树的中心。定义树的中心为“到所有点的最大距离“最小的节点，距离中心最远的节点一定是任一直径的端点，于是找到离端点最大值最小的那个顶点，就是中心。于是可以说，所有直径都经过树的中心，该中心将任一直径分割为长度差值最小的两段。

对树上一段长度有限的链，树上任意点到达这条链的最大距离称为偏心距。在使得偏心距最小的情况下，可以证明：1 该链一定在直径上；2 该链一定经过直径中心；3 无论该链在哪条直径上，所求出的最小偏心距都是一样的。

3 只有a1~b1直径上的点i才满足这个条件：dis(i,a)+dis(i,b) = dis(a,b)，否则总有dis(i,a)+dis(i,b) > dis(a,b)。

4 对于一棵树，如果在一个点的上接一个叶子节点，那么最多会改变直径的一个端点

求法：树形dp。相比之下，dfs不仅需要执行两次，在处理边权可负的树的直径时也稍显复杂，而树形dp可以优雅地解决这一问题。dp原理：最长树链必然可以表示为某一确定节点的一或两条最大向下链之和，因此可以在维护最大向下链的同时“顺便”更新树的直径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void fun(int x,int f)//dp[x]表示x节点的最长向下链，链终点用to[x]记录
{
    fa[x]=f;
    to[x]=x;
    dp[x]=0;
    for(auto i:G[x])
    {
        if(i.first!=f)
        {
            fun(i.first,x);
            if(dp[x]+dp[i.first]+i.second>maxlen)//maxlen是所求的树的直径
            {
                maxlen=dp[x]+dp[i.first]+i.second;
                st=to[x];//新起点
                ed=to[i.first];//新终点
            }//以st为根重新建树认父，即可还原从ed到st的路径
            if(dp[i.first]+i.second>dp[x])
            {
                dp[x]=dp[i.first]+i.second;
                to[x]=to[i.first];
            }
        }
    }
}

（个人）关于“求树上一点与其相距最远点的距离”的预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dt[maxn];
int mt[maxn],dd[maxn];//mt[x]记录x节点往最大深度的子节点，dd[x]记录x节点的次大深度
void dfs(int x,int f)
{
    for(auto p:G[x])
    {
        if(p.first!=f)
        {
            dfs(p.first,x);
            if(dt[x]<dt[p.first]+p.second)
            {
                dd[x]=max(dd[x],dt[x]);
                dt[x]=dt[p.first]+p.second;
                mt[x]=p.first;
            }
            else
                dd[x]=max(dd[x],dt[p.first]);
        }
    }
}

个人心得：

最长树链必然可以表示为某一确定节点x的一或两条最大向下链（我称为端链）之和，可表示为直径”具有一支或两支“。这样的x不止一个，对节点x的子树进行讨论：（边权为正）

1 若x仅有一个子节点，则直径仅一支。 2 x的子节点多于一个，且其子节点j具有唯一最长端链，则所有直径必有一支必沿子节点j向下。3 若最长端链唯二，或次大端链唯一，则直径的两支必沿这两个子节点向下。

4 两支的长度a,b是确定的，且两支的具体路径相互独立（只需总长为a或b即可）。

5 在某一支向下的途中，若遇某一点分叉，则所分叉方向的局部路径长度相同，这是显然的。结合4可知，若无根树的任意直径上一点p存在多条等长端链，那么也会再产生多条不同直径。

6 Floyd算法可以处理出所有树上所有最长路径。

（二）树上倍增

倍增的思想是二进制，通过在nlogn的时间内可以通过一遍dfs处理出这棵树的相关信息。然后就可以在logn的时间内完成对任意一条树链的操作（通常只能查询）。

通过树上倍增处理的问题，都是基于求LCA的过程，在该过程中“顺便”统计某些信息。

设fa[x][k]表示节点x向上跳跃2^k后的祖先节点，其中fa[x][0]为x的父节点。则$fa[x][k]=fa[fa[x][k-1]][k-1]$。用类似的思想可以维护更多数组，比如：

dis[x][k]表示x到fa[x][k]的路径边权和，则$dis[x][k]=dis[x][k-1]+dis[fa[x][k-1]][k-1]$。

mx[x][i]表示x到fa[x][k]的路径最大边权，则$mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1])$。

1
2
3
4
//用dfs中预处理
for(int i=1;(1<<i)<=dep[now];i++){//向上跳的层数(1<<i)<=节点的深度dep[now]
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }

倍增法求lca的过程如下，通过代码即可理解该算法。为了节省运算，以2为低的对数lg[x]需要预处理，lg[x]=(int)log2(x)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    while(dep[x]>dep[y]){
        x=fa[x][lg[dep[x]-dep[y]]];
    }
    if(x==y)return x;//记得加此特判，以防最后输出成fa[lca]
    for(int k=lg[dep[x]];k>=0;k--){//简单的二进制分解原理
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}

（三）树链剖分

重链剖分

在dfs序一章中，我们并未规定优先向哪个子节点递归。如今，定义每次先向重儿子进行递归，对dfs序采用线段树维护，可以同时实现多个修改和查询功能。

定义如下数组：deep[v]表示v的深度(根深度为1)，siz[v]表示v的子树的节点数，top[v]表示v所在的重链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），pos[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置（其实就是此前的l[v]或dfn[v]）。r[v]表示v的子树在dfs序中的右边界。

重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点。
重边：点v与其重儿子的连边。
轻边：点v与其轻儿子的连边。
重链：由重边连成的路径。

在这样的图中，所有点被唯一的重链所经过，每条重链的头部（根除外）通过一条轻边接入其他重链。

性质：

1 （核心）从任意一个点出发，到根节点的路径上不会经过超过 log(n) 条重链。换句话说，不会经过超过 log(n) 条轻边。

2 一条重链的向下终点，一定是叶子节点。也就是说，指定任意节点，其所处的重链，上端不一定是根，但下端一定是叶子。

（证明：我们发现，对于 x 的一个轻儿子 y，y 的子树大小肯定是小于 x 的子树大小的一半的。那么我们考虑极端情况，从根节点往任意一个节点走，设 size 为当前点的子树大小，那么每经过一条轻边，size就会除以2，因为 size 是不可能小于 0 的，所以最多经过 log(n) 条轻边。）

树链剖分分析

（图中的5、12、8、10所处的重链只有一个结点，自己就是重链头）

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs2(int x,int tp)//当前点以及当前点所在重链的顶端
{
    top[x]=tp;//更新每个点所在的重链的顶端 
    pos[x]=++cnt;//得到每个点的dfs序（新编号） 
    past[tot]=x;//记录每个新编号对应的原来的点 
    if(son[x])dfs2(son[x],tp);//优先往重儿子那里走 
    for(int i=first[x];i;i=e[i].next)
    {
        int y=e[i].y;
        if(y!=son[x]&&y!=fa[x])dfs2(y,y);
    }
    r[x]=cnt; 
}

当son[v]存在（即v不是叶子节点）时，显然有$top[son[v]] = top[v]$；对于v的各个轻儿子u，显然有$top[u] = u$。top[u]还可以看做是每条重链的代表节点。

在所得到的dfs序中，大体性质如之前所述，此外，每条重链的节点在序列中是一段连续区间，每条重链头挨着前一条重链的尾巴，且序列中所有重链的顶端节点深度由小到大。

树链剖分的操作原理，集中于lca的求解（树剖求LCA的最复杂情况是logn，但是实际上要达到logn是较难的，常数上也小，因此一般要比倍增快很多）。由以下代码理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);//使得x所在的重链顶端比y深，并优先在x处向上跳
       	//updata(1,pos[top[x]],pos[x],z);//线段树-区间赋值，表示对一段路径赋值z
        //res+=query(1,pos[top[x]],pos[x]);//线段树-区间查询，返回一段路径的长度
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])
        swap(x,y);
    //updata(1,pos[y],pos[x],z);
    //res+=query(1,pos[y],pos[x]);
    return x;
}

由于我们不再对路径赋值使用差分，那么对于子树求和，直接求$query(1,pos[x],r[x])$即可。自此，一般树上操作就被完全转化为了序列操作。

树链剖分维护dp

先证明一个命题

在树上任意节点，收齐来自其所有轻子孙（轻子树下的所有节点）的信息（如编号），总空间复杂度为$O(nlogn)$。

证明：任意节点的信息，只会被保存在它到根节点的路径上，由轻边所连接的祖先中。由于轻边不超过logn条，可知命题成立。

于是我们发现，如果将任意节点的来自子节点的转移信息，分成轻子树、重儿子，独立维护，那么当一个节点被修改时，只会影响到logn个节点，从而可以将复杂度降到logn层面。

树链剖分的实际常数较小，即使算上维护轻儿子信息的时间开销，只要我们对最终时间复杂度的评估可行，那么一般不会被卡。

在树形dp中，一旦树中权值改变，我们不得不从受改变的位置出发，将其到根的节点重新dp，复杂度O(n)。而借助树链剖分，我们有希望将每次修改的影响降到logn。

给定一颗树，树边有边权，每次修改一条边的边权，要求输出当前树的直径的长度，强制在线。

长链剖分

（四）树上启发式合并

树上启发式合并（dsu on tree）用来处理这样一类题目：询问支持离线，并且询问与子树有关。它可以很方便地在O(nlogn) 内完成答案的统计。
我们基于这样一个简单的问题来讨论dsu on tree。U41492 树上数颜色 - 洛谷

给定一棵节点具有颜色的树，询问每棵子树中有多少种不同的颜色

（1）树上莫队：这个十分简单，我们不多赘述。时间复杂度为$O(n\sqrt n)$

以下介绍两种启发式合并的方法：

（2）树上桶合并：我们把每个节点子树中的颜色编号存于一个set桶中，显然我们只需获取桶的大小即可（我不确定size()函数是否会导致复杂度升级，最好还是维护sz数组）。在桶往上传时，我们总是把小桶合并到大桶，于是可以保证每个元素被移出桶的次数最多只有logn。这样做的复杂度为$O(nlogn)$，考虑到set的操作是logn的，于是总复杂度为$O(nlogn^2)$，能勉强应付1e6的数据。

（3）树上启发式合并：

先论暴力算法。我们维护一个计数数组cnt，记录某颜色当前的数量，当cnt[x]由0变1时++ans。对每个节点，重置ans和cnt，然后遍历以它为根的子树，最后把ans记录在该点上。

而树上启发式合并基于的就是对$O(n^2)$的优化。对于一个结点u，我们不一定非要在被清空的cnt和ans上重新开始，因为u的儿子子树的信息同样是自己的一部分，所以可以在其某个儿子遗留的未重置的cnt和ans上接着维护ans。我们指定这个儿子为重儿子，能使总复杂度达到O(nlogn)。

证明：每个节点除了最原始的遍历，在它到根节点的路径上，每有一条轻边就意味着要被多遍历一次。由树链剖分的引理可知，从根到任一节点的链上最多只有logn条轻边，于是每个节点最多被遍历logn+1次。

算法步骤：

1 预处理每个点的重儿子

2-1 进入dfs函数，函数首先向非重儿子方向递归，完成这些节点的处理，这主要是为了自下而上出结果。dfs函数默认不清除数据，因此要手动清除。

2-2 接着才正式开始启发式合并。具体见如下参考模板。

参考模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void dfs0( int u, int fa ) { //遍历整个树，找每个点的重儿子
	siz[u] = 1;
	for( int v : G[u]) {
		if( v == fa ) continue;
		dfs0( v, u );
		siz[u] += siz[v];
		if( siz[v] > siz[son[u]] )
			son[u] = v;
	}
}

int ans; //记录答案的全局变量，跟随全局数组一起重置

void calc( int u, int fa, bool flag ) {//遍历以u为根的子树，处理每个节点的数据
	if( flag ) { //flag=0回退 flag=1添加
		//统计数据
	}	
	else {
		//按原路清理数据（通常是彻底清除，直接赋0、inf或-inf）
	}
	for( int v : G[u] )
		if( v != fa ) calc( v, u, flag );
}

void dfs( int u, int fa ) { //默认不清理遗留数据
	for( int v : G[u] ) {
		if( v == fa || v == son[u] ) continue;
		dfs( v, u );//先算轻儿子的答案
		calc( v, u, 0 );//计算完轻儿子的答案后 要把儿子的痕迹擦干净 为下一个儿子准备
        ans=0;//或+-inf
		//...可能还有其他的操作
	} //以下才是启发式合并的正式开始
	if( son[u] ) dfs( son[u], u );//重儿子的贡献仍然保留 不回退
    //别忘了把u本身加入数据
    //如果重儿子遗留的ans不是我们需要的，还得重置一下
	for( int v : G[u] ) {
		if( v == fa || v == son[u] ) continue;
		calc( v, u, 1 );//开始重新添加每个轻儿子的贡献 为后面计算自己准备
	}
	//...一堆操作，比如将ans计入res[u]，或者处理挂在u上的询问
}

个人总结：

（1）保证每个节点只被dfs一次，被calc不超过logn次

（2）清除数据不能用memset，而按其怎么加进来去原路把数据清除，这样防止了复杂度退化。

（3）calc函数的功能是遍历子树记录子孙节点数据，如果这些节点的数据是给定的或者有办法预处理，还可以通过提前生成dfs序，来代替遍历子树。

（4）树上启发式合并的典型运用：Problem - D - Codeforces（神题，多细品）。 以0/1表示22个字母分别出现奇数次还是偶数次，我们所维护的数组叫做len，len[s]表示从根到某一节点形成的01串s的最大深度（启发：节点记录的数据要么与本点绑定，要么就相对于根节点），节点的s和深度都是可以预处理好的（这样刚好能由两点01串的异或得到两点的路径信息）。对于当前节点u，我们的目标是找到经过u的最长合法路径。对u的每棵轻儿子子树，要进行三次calc，第一次是遍历子树中的节点x，从现有的len集合中找到所有与x形成合法匹配的01串s，用dep[x]+len[s]-2*dep[u]来更新ans，第二次是把子树中所有节点x的01串s更新到len集合，也就是len[s]=max(len[s],dep[x])。第三次是清空len，注意要重置为-inf而不是0。这道题目显然无法采用莫队，因为第一次calc和第二次calc是严格分开的。

（五）点分治

点分治适合处理大规模的树上路径信息问题。

我们先随意选择一个节点作为根节点 ，显然所有路径都可以划分为两种：经过根的和不经过根的，我们以寻常处理路径的方式，统计前所有经过根的路径信息（也就是统计从根出发的向下链，两两拼接组成路径），然后进入各子树，继续以各子节点为根统计经过根的路径，直至叶子节点。这样便统计了所有路径的信息，但是效率并不高。

考虑如果每次在进入子树进行同样的处理时，重新选取其重心为根。我们知道，如果当前树的大小为N，那么重心的任何子树的大小都不超过N/2，也就是说，solve函数的递归深度不超过logn。考虑每层递归累计复杂度为O(n)，于是得出总复杂度为O(nlogn)。

点分治是这样的一个过程：以分治重心为根，对其分治区域重整成树，然后再O(n)统计出包含根在内的所求数据（比如路径、连通块），不经过根的数据再进入子树继续分治。可以保证，点分治过程中可以对所有路径进行查询。

参考模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
int sz[maxn];//表示当前树中以某节点为根的子树大小
int mxsz[maxn];//表示当前树中某节点的最大支的大小。初始化mxsz[0]=inf
int vis[maxn];//标记删除的点，禁止向其搜索，这样其各支就相当于分离了
int judge[10000007];//我们要维护的查询表。同往常一样，每次不能暴力清空
int rt,tot; //tot表示当前树的总大小。这两个量要在递归进入每个solve时重置
int n,m;

void get_root(int x,int f) //将rt更新为当前树的重心
{
    mxsz[x]=0,sz[x]=1;
    for(auto p:G[x])
    {
        int i=p.first;
        if(vis[i] || i==f) continue;
        get_root(i,x);
        mxsz[x]=max(sz[i],mxsz[x]);
        sz[x]+=sz[i];
    }
    mxsz[x]=max(mxsz[x],tot-sz[x]);
    if(mxsz[x]<mxsz[rt]) rt=x;
}

void calc(int x,int f,int mode)
{
    //...
}

void solve(int x) //与寻常分治不同，点分治是自上而下的，即先处理以本点为根的树，在递归处理其子树
{//一定要确保x是所在子树的重心
    for(auto p:G[x])
    {
        int i=p.first;
        if(vis[i]) continue;
        calc(i,x,0);//计算
        calc(i,x,1);//录入
    }
    for(auto p:G[x])
    {
        int i=p.first;
        if(vis[i]) continue;
        calc(i,x,2);//清除
    }
    vis[x]=1;
    get_root(x,0); //以x为根dfs重置sz数组（很经典的漏洞，会导致重心找错从而影响算法效率）
    for(auto p:G[x])
    {
        int i=p.first;
        if(vis[i]) continue;
        tot=sz[i]; //这里的sz[i]不会被下面的get_root影响，因为x的各个子节点在不同的连通块中
        rt=0; //这里不可取rt=i
        get_root(i,x); //将rt更新为“结点i所在的树的子图”的重心
        solve(rt);
    }
}

点分治和树上启发式合并能处理的问题，是一种交集的关系。树上启发式合并的优势在于，可以一次性预处理出以任意点为根的子树的信息；点分治的优点在于，对于每个根节点，我们用最原始暴力的O(n)算法遍历所有树节点即可。它不要求继承来自重儿子的信息表，比如在一些问题中，我们不得不把重儿子子树也遍历一遍（来自重儿子的信息表不能对其父节点提供有效帮助），这时点分治便起作用了。

（在【模板】点分治中，我们也可以用树上启发式合并来解决，其中信息表ar[x]记录x到根的距离）

树上连通块

常见的问题为，对于树上的所有连通块，统计其中合法方案的数量。我们以重心为根，把连通块分为两类：包含根的和不包含根的。对于前者，既然包含根，那么该连通块就一定可以通过在树上删除若干个子树得到，这就相当于在dfs序中删除若干连续区间，从而将问题变为了线性dp问题；对于后者，则进入各个分治区域，继续重复操作。

hdu5909 Tree Cutting

给一颗树，结点带权值v[i]<m。求异或和为k的连通块个数（0<=k<m，n,m<=1000）。

此题的核心代码，套在点分治中——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
long long dp[maxn][1500]; //**dp[i][j]表示dfs序中1-i的状态为j的总方案数**
long long res[1500];
void solve(int x)
{
    tim=0;
    dfs(x,0);//对分治区域，生成dfs序
    dp[1][ar[x]]=1;
    for(int i=l[x];i<r[x];++i)
    {
        int t=sa[i+1]; //表示dfs序中i位置后的下一个元素
        for(int j=0;j<m;++j)
        {//下一个元素选与不选。考虑到状态间存在依赖性，为了方便我们采用从前向后贡献的方式转移状态
            (dp[i+1][j^ar[t]]+=dp[i][j])%=mod;
            (dp[r[t]][j]+=dp[i][j])%=mod; //根据状态描述，这里把状态转移到r[t]，不要写成r[t]+1
        }
    }
    for(int j=0;j<m;++j)
    {
        (res[j]+=dp[r[x]][j])%=mod;
    }
    for(int i=0;i<=tim+1;++i)
        for(int j=0;j<m;++j)
            dp[i][j]=0; //消除本次修改
}

点分树（动态点分治）

点分治的核心思想在于依据重心划分子连通块，其良好的性质保证了最多只会分治 logn 层。有了这一特性，便可使用各种暴力计算答案。那么我们按照分治递归的顺序提一颗新树出来，易知树高是 O(logn)的，称之为点分树。

具体的性质，在博客中有完整的阐述。概括如下：

  • **点 x 在点分树上的子孙集合就是原树中以 x 为重心（分治中心）时的分治区域，点分树上所有点的子树大小之和为 O(nlogn) **（每个点会被从根到它的路径上最多 logn 个祖先所统计）。这意味着，即便在每个节点上保存所有子孙的信息，空间复杂度只是O(nlogn)的。
  • 点分树的树高为 O(logn)。这意味着，如果要对某个点进行修改操作，直接在点分树上暴力跳父亲，改变 O(logn) 个祖先的子树信息即可。统计亦同理。
  • 对于点分树上 x 与 y 的 lca（或者说囊括连通块同时包含 x,y 的所有点分树节点中深度最深的那一个），易知在以此点为重心划分子连通块时 x,y 会首次被分割开来，因此该点必定在原树的 x,y 路径上。我们采集y对x的贡献，仅需从该lca上读取信息。
  • 点分树的一个子树总是原树上的一个联通块。在点分治过程中到达点u时，u的子节点数量在原树（当前树以u为根，除去已被标记的点）和点分树上是相同的，且一一对应，即，u在原树的不同儿子处在不同次级分治区域中内，获取来自某一儿子的信息，相当于获取来自对应的点分树子节点的信息。
  • 节点x的分治区域被包含在y中，当且仅当y是x的祖先，也就是说，只有x的祖先记录了以x为终点的链，x的子孙节点的分治区域中不包含x，而其余的节点的分治区域则与x独立。点分树上，各分治重心所负责的路径互不重复。

点分树的每个节点u，都可以看作是这样一棵树，它包含u的分治区域，并以分治重心u为根，负责统计（部分）经过u的路径。与根直接相连的各个子树，就是u的点分树子节点的分治区域。当一个点、一条边被修改，影响的是这棵树中的某一子树（联想DFS序），我们可以建立数据结构来维护这棵以u为根的树。

点分树的常数相当大，$O(n(logn)^2)$的复杂度甚至往往只能应付1e5而不能应付2e5，所以除了要细心降低常数外，我们在一个点分树节点上套数据结构时也得慎之又慎。由于每个节点所代表的分治区域大小总和不超过nlogn，我们在一个点分树节点上套数据结构，可以该结构的大小设置为以此节点为分治中心时的连通块大小（一般得再多预留一点空间）。

特别地，如果边权为1，那么从某一节点出发到其分治区域的任一点的链长，都不会超过连通块大小，我们可以使用静态表vector来O(1)地记录与读取某一长度的链的信息，而不是用map。考虑到连通块内的点数同样有限，我们可以在vector下再套vector来存放点编号，这都是允许的。

点分树和原树在结构上关联甚小，一定不要认为点分树上相邻节点在原树上也是相邻的。

能解决什么问题？

通常而言，点分树是一种维护端点链的工具，在具体问题中可以灵活运用。

一类典型的题目就是，指定树上一点，求与此点的路径长度满足一定条件的其他所有点的贡献之和，在需要时还得支持在线和带修。对于点分树节点u所代表的连通块中每个节点v（在进入这个连通块时，u为根），将端点链u-v的信息、贡献保存在u中（记作F1[u]），可以保证所有节点保存的链都是独立的，且可以组成树上的所有路径。对于指定的原树点x，以x为端点的路径，一定只能从“x到x在点分树上的祖先（含x本身） + 该祖先所记录的某条不位于x所在的子连通块的链（含该祖先单独本点，这经常被忽略）”组成（注意切勿把x在点分树的祖先与原树的祖先混淆）。假设v是u的子节点（点分树上），将v所代表的连通块（含有x）的所有点对v的父亲（这是确定且唯一的）的贡献保存在v中（记作F2[v]），在对x求解时额外减去这些贡献即可。

可以通过O(1)求LCA的方式来节省求两点路径的logn开销（题外话，树剖在一般情况下能与ST表不分上下）。不过考虑到我们一般只求点分树上节点到其祖先的距离，而祖先数量又不超过logn，我们可以对点分树执行一次预处理达到同样的效果。

1
2
3
4
5
6
7
8
9
10
long long query(x) //这是个大致模式参考
{
    long long res=F1[x];
    for(int y=x;fa[y];y=fa[y])
    {
        long long d=dis(x,fa[y]); //原树上的路径的距离，这个信息在很多题目要用到
        res+=F1[fa[y]]-F2[y];
    }
    return res;
}

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

点分树是对点分治过程的实质化，不难发现，点分治过程就是在这棵树上的DFS。

P2056] 捉迷藏 在点分树上，节点x的信息只保存在其祖先节点中，x受到改动也只会影响的祖先记录的结果，于是修改其祖先的信息、重新更新祖先的结果，并维护全局答案即可。对于x的某个祖先y，其记录的是在以y为根的分治区域树中，经过y的最长路径，因此它只在意各个子树的最长链，我们可以用multiset来维护。点分树中所有节点所记录的结果的最大值，就是全局解，我们还是用multiset来维护这n个分治重心的结果，当一个分治重心的结果改变时，重新维护全局解。

同样的，从点分树根节点到某一节点的决策路径，也可以看做是不断细分的过程，类比二分，这适用于一些有单调性质的问题。比如说越靠近某一个靶点，点值会越大/越小。具体地讲，我们确定目标节点一定在原树某一个连通块内，根据“点分树的一个子树总是原树上的一个联通块”这一重要性质，我们从点分树根节点出发，一路向下，不断地缩小连通块（如果原树中u的子节点v更优，可移动到v所在的连通块），最终就能找到靶点。

以P3345]幻想乡战略游戏为例：

1
2
3
4
5
6
7
8
9
10
11
12
ll sea(int x)//传至此节点的点权和以及总贡献
{
    ll me=query(x);
    int vn=G[x].size();
    for(int i=0;i<vn;++i)
    {//在原图上做决策，在点分树上做移动
        if(query(G[x][i].first)<me) //本题（求点带权重心）的性质：非重心的节点，至少有一个邻节点的值小于自己
            return sea(Gx[x][i]); //我们在建树时，x在原树的每个邻节点恰好对应x在点分树的子节点，从而可以快速找到该邻节点所在的连通块的重心
        //由于单调性，一定不会回到x在点分树的父节点
    }
    return me;
}

那么我们在建树时，可以——

1
2
3
4
5
6
7
8
9
10
11
12
for(int i:G[x]) //遍历邻点
{
	if(vis[i]) 
    {   
        Gx[x].push_back(i); //x在点分树的父节点
        continue;
    }
    tot=sz[i];
    rt=0;
    get_root(i,0);
    Gx[x].push_back(rt);
}

（六）虚树

在一类树上动态规划问题中，题目给出的询问往往包含树上的若干节点，并保证总的点数规模小于某个值。

如果我们对每个询问，都直接在整颗树上进行dp的话，时间复杂度显然是不可接受的。如果我们可以找到一种动态规划的方法，使其时间复杂度与询问中点的实际规模相关就好了，于是虚树应运而生。

对于每次询问给出的若干节点，称之为关键点，虚树即是一棵虚拟构建的树，这棵树只包含关键点以及任意两个关键点的lca（称作关键lca），而其他不影响虚树结构的点和边都相当于进行了路径压缩。显然虚树的叶子节点必然是询问点，因此对于某次含有 k 个点的询问，虚树最多有 k 个叶子结点，从而整颗虚树最多只有 2k−1个结点（这会在虚树变成二叉树形态时达到）。对于每次询问，我们只需在O(k)或(klogk）求出答案即可。

vtree-6

构建过程

首先将给出的若干关键点，按dfs序排序。我们维护一个栈，从栈顶到栈底的元素始终形成虚树的一自上而下的树链（这表示从栈底到栈首的dfs序是递增的，也就是说这是单调栈）。随后我们遍历关键点，执行这样的插入过程：

1.如果栈为空,或者栈中只有一个元素,那么显然应该: stk[++top]=u;
2.取lca=LCA(u,stk[top])，如果lca=stk[top]，则说明uu点应该接着stk[top]点延长当前的树链.做操作:
stk[++top]=u;
3.如果lca≠stk[top]，则说明u与stk[top]分属lca的两棵不同的子树，且包含stk[top]的这颗子树应该已经构建完成了。我们需要做的是：将栈中包含在lca子树下的那部分节点退栈，并将这部分建边形成虚树。如果lca不在栈(树链)中，那么要把lca也加入栈中，保证虚树的结构不出现问题，随后将u加入栈中，以表延长树链。

一些思想：

  • 建树过程中，每次所连的两边总是祖孙关系

  • 为了便于DP，我们一般使栈底为根节点（不可能会在关键点插入途中被弹出）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insert(int u){
    if(top <= 1) {stk[++top] = u;return;}
    int lca = LCA(u,stk[top]);
    if(lca == stk[top]) {stk[++top] = u;return ;}
    while(top > 1 && dfn[lca] <= dfn[stk[top-1]]){
        add_edge(stk[top-1],stk[top]);
        --top;
    }
    if(lca != stk[top]) {
        add_edge(lca,stk[top]);
        stk[top] = lca;
    } 
    stk[++top] = u;
}

完成插入后，最后还需将栈中元素弹出（除了底部）

1
2
3
4
5
while(top>1)
{
	add_edge(st[top],st[top-1]);
	--top;
}

在遍历虚树时，我们在回溯时顺便逐一清空边集

1
2
3
4
5
6
7
8
9
void dfs(int x) //树形dp
{
    //...
    for(auto p:Gx[x])
    {
        //...
    }
    Gx[x].clear(); //即将回溯时，顺便清空边集
}

5、树的环

（一）基环树

基环树，又称环套树，最显著的特点就是有 N 个点 N 条边。如果在树上再加一条边，则必然会形成一个环，以环上每一点为根，其下都有各自的子树，这就是基环树的典型结构。

查看源图像

如果不保证图是连通的，比如说，只是简单描述“每个节点都额外有一条连其他节点的边”，那么所形成的图为基环树森林，其在每个连通块均存在一个环，在这一点上一定要留心题意！

在基环树的dfs树中，有且只有一条返祖边/回边，如下图所示。

查看源图像

在解决基环树问题时，通常需要单独抽出基环，再逐个以环上节点为根作普通树进行独立处理，最后在环上合并结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void dfs(int x,int f,int e) 
{//to[x]表示x在环中与下一点的距离
	dfn[x]=++tim;
	to[x]=e; //父边边权
	fa[x]=f;
    for(const auto &p:G[x])
    {
        int i=p.first;
        if(!dfn[i])
            dfs(i,x,p.second);
        else if(dfn[i]<dfn[x]) //这里找的是向上回边，也可以采用找向下回边来记录环
        {
            int y=x;
            rd.emplace_back(); //vector<vector<int> > rd; int cnt;
            while(y!=i)
            {
                rd[cnt].push_back(y);
                y=fa[y];
            }
            rd[cnt].push_back(i);
            to[i]=p.second; //连接回边两端点的边长为回边的权值
            ++cnt;
        }
    }
}

在环路上求$max(Ai+Aj+dist(i,j))$，其中$dist(i,j)$表示i到j的环上最短距离。首先，我们将环从一点断开为链，复制一份然后头尾衔接。考虑到$dist(i,j)$一定小于等于环长的一半，我们可以将$Ai+Aj+dist(i,j)$分为$Ai+dis[i]$和$Aj-dis[j]$两部分之和，其中$dis[i]$表示i到序列起点的距离，然后跑单调队列，维护一个长度小于等于半环长的滑动窗口的最大值。

单调队列方面容易出错，要时常温习。以下是将$dist(i,j)$的定义改为i到j的环上最长距离，其余要求不变的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct dat{
	long long val,d; //d表示到序列起点的距离
}q[maxn*2];//注意由于断环为链，长度应翻倍

int m=rd.size();
for(int j=0;j<m;++j)
	rd.push_back(rd[j]);
a=1,b=0;//队列置空
long long s=0;
for(int j=0;j<m;++j)
    s+=to[j];
long long bs=s/2;
int vn=2*m;
long long dis=0;
for(int j=0;j<vn;++j)
{
    int t=rd[j];
    while(dis-q[a].d>bs && a<=b)
        ++a;
    if(a<=b) //不可少此判断
        res=max(res,dt[t]-dis+q[a].val);
    long long tem=dt[t]+dis+s;
    while(q[b].val<=tem && a<=b)
        --b;
    q[++b]={tem,dis};
    dis+=to[t];
}

另外一种思想是，先无视这条回边，转换为树上问题解决，再考虑返祖边带来的影响。

给出一个 N 个点 N 条边的连通图，每个点有点权，求出其最大独立集（不能选取相邻的节点情况下能选取点集的最大点权和）只是提供思想借鉴，这道题也可以树上dp加环上dp

假如我们已经把这条回边的两个端点找了出来，设为 lt 和 rt，不难发现，对于最后的答案选取情况无非 3 种，一是 lt 选 rt 不选，二是 lt 不选 rt 选，三是 lt、rt 都不选

我们可以把这三种情况都计算出来，先强制不选取 rt，然后以 lt 为根在忽略回边之后的树上跑最大独立集，可以得到当 lt 选/不选并且 rt 不选的时候得到的最大答案，然后强制不选取 lt 再以 rt 为根跑一次就能得到选取 rt 并且不选取 lt 的最大答案，三者求最大值即可。（如果是基环树森林，只需累和每棵基环树的结果）

有向基环树（内向树和外向树）

“每个节点有且只有一条出边”——

考虑一棵有向树，每个节点的父边沿根方向，此时从根节点出发，连一条指向其它任一节点的有向边，这便形成了内向树结构。问题所描述的图是内向树森林。

查看源图像

外向树同理，这里不多赘述。（之前提到的“水母图”就是外向树）

（二）仙人掌图

回忆DFS树部分的内容，仙人掌图的DFS树中，每条边只被最多一条回边所覆盖。

微信图片_20220730232143(1)

可以知道，普通树和基环树，都是特殊的仙人掌图，因此可以归为一类去处理。

我们从求仙人掌图的直径（两点最短路径最大值）这个经典的问题入手：

（1）定义以u节点为根的子仙人掌为，将u的能向根节点移动的边移除后，u所在的连通块。如对于4号节点，应移除4-5、4-3，4所在的剩余部分（4, 7, 8, 9）即为以4为根的子仙人掌。显然，以u为环根的环，也包含在以u为根的子仙人掌中。

（2）图的DFS树中被回边所覆盖的部分，就是图中的环。我们把每个环第一个被遍历到的节点叫做环根，如上图的2、3、4、10号节点。设$dt[x]$为在以x为根的子仙人掌中，离x最远的节点的距离（不一定是叶子），如dt[4]=2（4号为环根，可以通过7号到9号节点，但不能通过5号到6号节点）。

（3）设v为u的一个子节点。

若$low[v]<dfn[u]$，则dt[u]不接受dt[v]的更新。

若$low[v]>dfn[u]$，说明树边u-v为桥，可按普通树形式用dt[v]更新dt[u]。

如果$low[v]==dfn[u]$，那么说明u为环根（u可以是多个环的环根）。设k为环上其余各点，则$dt[u]=max{dt[k]+dist(k,u)|k}$，其中$dist(k,u)$为k与u的最短距离，设环长为s，有$dist(u,w)=min(deep[k]-deep[u],s-(deep[k]-deep[u]))$。

（4）对于每个节点，在更新dt[u]时（即$low[v]>=dfn[u]$时）顺便更新经过u点的直径（u子树下）。对于$low[v]==dfn[u]$，还需要对u所在环，处理u子树下出经过该环的最长路径，即求出最大的$dt[x]+dt[y]+dist(x,y)$，我们可以采用单调队列，具体可参考基环树部分。（环上进行单调队列时，dt[u]不需要特殊处理，因为不影响总直径结果）

在其它仙人掌上的DP问题中，也大多是采用这种思想——环上非根点只记录不经过环的信息，在到达环根时，再通过环形DP遍历环点将答案累计给环根。（如求仙人掌的最大独立子集）（设环长m，分别固定环起点取或不取来跑DP，得到的dp[m][0]和dp[m][0]+dp[m][1]中较大者即解）

（三）圆方树

仙人掌&圆方树学习笔记 - 小蒟蒻yyb - 博客园 (cnblogs.com)

圆方树——处理仙人掌的利器 - 博客 - immortalCO的博客 (uoj.ac)

为了更便捷地处理仙人掌问题，对于一个环，我们将所有环边断开，将每个环点连接到一个新点上，这个新点叫做方点，原图中的点称为圆点。不能看出，经处理后，新图为树形结构，称为圆方树。

img

仙人掌-圆方树具有如下重要性质：

（1）无论取原图中哪个点为DFS树的根，圆方树的形态是一样的。

（2）仙人掌图以u为根的子仙人掌下的所有节点，就是圆方树中以u为根时，u子树下的所有圆点。

（3）方点不会与方点相连，

具体的断环操作是，在DFS树上，令环上非环根点的父亲节点，改为新开的方点sq，然后令fa[sq]=环根。通过Tarjan预处理出所有点的父节点（及父边权），然后建圆方树的图。

广义圆方树

对于一个无向图，我们将一个点双连通分量内的所有边删去，再将点双连通分量中的每个点向一个新建的点连边，这个新建的点即是方点，原图中的点为圆点，形成的树结构称为（广义）圆方树。

img

所以在圆方树中有$ n + c $个点，其中 n 是原图点数，c 是原图点双连通分量的个数。广义圆方树是一颗完美的树，它具有以下性质：

  • 圆方树中每条边连接一个圆点和一个方点，圆方树上任意一条路径上圆点方点间隔分布，方点之间不会存在连边。两圆点在树上路径中所经过的圆点（割点），就是这两点在原图上所有简单路径的必经点。
  • 原图的割点就是圆方树中度数大于 1 的圆点，非割点都是叶子节点，叶子节点不可能是方点。
  • 如果以圆点为根，那么方点的父亲一定是圆点（反之不然，要特判根）；如果以方点为根，那么圆点的父亲一定是方点。两圆点的LCA可能是方点，也可能是圆点。
  • 对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双，即同一个点双中的两不同点 u ，v 之间一定存在一条简单路径经过给定的在同一个点双内的另一点 w。也就是说，两圆点在圆方树上的路径中，路径上经过的方点的相邻圆点的集合，就等于原图中两点所有简单路径上的点集。
  • 我们用方点来记录其所对应的点双的信息，作为对树上路径的整体贡献。对一条路径，只有当其经过一个方点时，才能认为经过了这个方点对应的点双。

当我们使用方点收集其相邻圆点的信息时（即统计eDCC信息），每修改一个圆点的值，就要更新其相邻方点的值，这样做的效率并不高。实际问题中，我们可以令方点收集的信息，来自该方点的所有子节点（一定是圆点），这样修改圆点的值时只需更新其父方点即可。考虑到一条树上路径 x - y ，一定恰好处在以节点k=lca(x,y)为根的子树中（且“披”在上方），如果 k 为方点，再用k的父圆点来更新结果。至于其他方点，其父圆点也一定处在 x-y 中，且恰好只被一个方点记录（k为圆点时除外）。

另外，关于点双中大小关系的信息（比如说eDCC中的最小点权），不好通过直接修改方点来维护。可以考虑在每个方点挂一个桶——multiset，修改圆点时，从父方点中erase旧值并insert新值。更复杂的，甚至可以在方点上套数据结构（总空间为2N）。

6、图的连通性

（一）Tarjan

bcc-1.png

在DFS树中一章中已经初步介绍了关于搜索树的内容。一条边为桥，当且仅当它不是回边且不被回边覆盖，如上图的黑色边。仅单纯判断一条边是否为桥，我们有很简单的做法——树上差分，将每个点作为其父边的唯一标志，我们为所有被回边覆盖的边赋值，并在最后判断值仍为0的边的数量。

Tarjan 算法是基于深度优先搜索的算法，用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥，进一步地可以求解无向图的双连通分量；同时，也可以求解有向图的强连通分量、必经点与必经边。它定义了两个关键值：

  • dfn[x]：节点x的时间戳
  • low[x]：以节点x为根的子树，通过回边能追溯到的最早时间戳。

这两个数组在每次做tarjan时需要重置。注意，如果允许重边存在，那么节点x就可能存在一条回边连接自己的父节点，为了将这条回边与x的父边区分开来，我们选用链式前向星建图。考虑到链式前向星中无向边的正反两边编号相邻，若以偶数为第一个边编号，则相邻编号的异或值为1，比如0^1,2^3。我们以2为第一条边的编号，那么e^1就是边e的反边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void tarjan(int x,int ind)
{
    dfn[x]=low[x]=++tim;
    for(int k=hd[x];k;k=nt[k])
    {   
        int i=to[k];
        if(!dfn[i])
        {
            tarjan(i,k);
            low[x]=min(low[x],low[i]);
            if(low[i]>dfn[x])
                bridge[k]=bridge[k^1]=1; //链式前向星中无向边的来回两边编号相邻，若以偶数为第一个边编号，则相邻编号的异或值为1，比如0^1,2^3。
            if(low[i]>=dfn[x])
            {
                if(x!=root || child>1)
                    cut[x]=1;
            }
        }
        else if(k!=(ind^1)) //如果与上一步不是同一条无向边（因为要考虑到两条边可能连接同一对点）
            low[x]=min(low[x],dfn[i]);
    }
}

桥 x->i 的判断方式是$low[i]>dfn[x]$，这与x是否为根无关。

但是对于割点，如果x为根，这意味着所有节点的low都不可能小于它，判断它是割点的唯一方式是其儿子多于1。

边双连通分量

边双连通图是指不含桥的图。将原图中的桥删除后，边得到了所有的边双连通分量。

  • 边双连通图中任意每条边都至少在一个简单环中，即所有的边都不是桥，桥也不属于任何边双，删去边双中的一条边不会影响整个边双的连通性。

  • 如果e为桥，那么e一定不在任何环中，否则至少有一个环包含e，这个环一定在e所在的eDCC内。

  • 两个树环属于一个边双，当且仅当它们有公共点。

  • 对于一个边双连通图，我们总有边的定向方案将其变成强连通图（见第一章）。同样的，将一张有向图中的一个强联通分量的每条边变为无向的，则这个强连通分量变为一个边双联通分量。

如果将边双缩点，就会得到一棵缩点树（或森林），树边为原图中的桥（如果原图存在游离的边双，那么新图就会出现游离的点）。从而我们把无向图的问题转到了树上，同时也保存了原来无向图的信息。

点双连通分量

点双连通分量是不存在割点的极大双连通子图。如果一个图是点双连通图，那么它不含割点。特别地，对于两点一边的图，也称之为点双。割点就算相邻也会属于至少两个vDCC。（游离点不在本节的讨论范围）

  • 点数大于2的点双连通分量中任意两点都同时包含在至少一个简单环中（这也是点双的充要条件），如果两点在不同的点双中，这两点不在任何一个简单环上。
  • 任意割点都是至少两个不同双连通分量的公共点，vDCC间的交点都是割点，任意非割点只属于一个点双联通分量。
  • 两个树环属于一个点双，当且仅当它们有公共边。
  • 任何点若被环经过，当且仅当该点所在的vDCC（1或2个）存在环。点双内的任意两条边都在同一个简单环中。
  • 对于点双中的任一点x和任一环A，总能找到一个环B（允许A=B），使得B经过x，且A和B有交集（证：当环数大于1时，每个环与至少一个环有公共边）。由此说明我们至少能找到两个环，它们有一段交集。
  • 点数大于2的点双一定是边双， 边双的不一定是点双（比如两环交一点的边双）。
  • 对于一个点双中的两点，它们之间简单路径的并集，恰好完全等于这个点双（点双中的任一点都能与其它两点成环），即同一个点双中的两不同点 u, v之间一定存在一条简单路径经过给定的在同一个点双内的另一点 w 。

奇环判定：DFS染色法。点双中有奇环，当且仅当存在一条边连接相同颜色。用染色法判断偶环会出现遗漏。

偶环判定：点双中有偶环，除了点双自身即为一个偶环外，当且仅当点双中的某一边被至少两个环经过。换句话说，如果一个点双不是一个纯环，即点双中存在度数大于2的点，那么点双中一定存在偶环。

求证：非纯环的点双一定有偶环。
在点双中任找一个环A和不在这个环上的一点x，由上述定理可知，存在一个环B经过x且与A有交集。当A, B都是奇环时，A∪B - A∩B所构成的新环长度一定是偶数。

求证：当点双中存在一个奇环时，点双中的每一点都至少在一个奇环中。

同上个证明类似，如果A是奇环，那么A, B交集部分长度既可以取奇数，也可以取偶数，从而一定能与B的剩余部分（A∪B - A）组成奇环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void tarjan(int x)
{
    dfn[x]=low[x]=++od;
    st[++up]=x;
    if(x==root && hd[x]==0) //如果是游离点
    {
        dcc[++cnt].push_back(x);  up=0;
        return;
    }
    for(int p=hd[x];p;p=nt[p])
    {
        int i=to[p];
        if(!dfn[i])
        {
            tarjan(i);
            low[x]=min(low[x],low[i]);
            if(low[i]>=dfn[x])
            {
                ++cnt;
                do{
                    int y=st[up];
                    dcc[cnt].push_back(y);
                }while(st[up--]!=i); //弹出至当前儿子
                dcc[cnt].push_back(x);
            }
        }
        else low[x]=min(low[x],dfn[i]); //求vDCC的过程允许从父亲更新low值；无向图没有横边，也无需判断是否在栈中
    }
}

强连通分量

强连通图是指任意两点均可互达的有向图。

  • low[x]表示在以x为根的子树中，通过向前边和有效的横向边，所能追溯到的最早时间戳。“有效”指的是横向边所指节点还在栈中。tarjan在实现中，如果一个节点未访问过，则以树边访问它；如果已访问过，又不在栈中，说明其早已成为另一个SCC的一部分，不可以从它更新自己的low值。
  • 如果一个顶点 v 的 low 等于它的时间戳，则该顶点一定是所属强连通分量的“根”（强连通分量中时间戳最小的结点）。我们在缩点时，有时就可以令当前SCC中的点的新 id 为这个代表点。
  • 将任意有向图转换为SCC，我们缩点使图成为(多个)DAG，每次抹除一个入度为0的点和出度为0的点，那么添加的总边数就是前后者总数中的较大值（特判游离的环）。

SCC最大的作用，在于将其缩点后，有向图将失去所有环，成为DAG图。在DAG上，无论进行拓扑排序+DP还是记忆化搜索，都有十分理想的时间复杂度。如果一个强连通分量对所有经过它的图上路径的贡献是确定的，我们就能将其缩为DAG上的一点。此类问题一般允许经过重复点。

在新的DAG图中：

  • 若采用原图缩点的方式，对于一个原图点，如果id[x]!=x，说明它不在缩点图上
  • 可能存在重边，一定要注意这对累和型记忆化搜索的影响

（二）并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：

  • 查找（Find）：确定某个元素处于哪个子集；
  • 合并（Union）：将两个子集合并成一个集合。

路径压缩和按秩合并

经过路径压缩后的并查集，其总复杂度近似O(1)，做法不再赘述。

然而在一些问题中，路径压缩的做法会导致失去大量信息。我们可以改用按秩合并的形式（“秩”即深度）：每次将深度低的树的根，指向深度较大的树的根，然后更新后者的深度。这保证了任意树的深度均不超过logn。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int find(int x)
{
    if(x==fa[x])return x;
    return find(fa[x]);
}
void join(int x,int y)
{
    int a=find(x),b=find(y);
    if(a!=b)
    {
        if(rk[a]>rk[b])
            swap(a,b);
        if(rk[a]==rk[b]) ++rk[b];
        fa[a]=b;
    }
}

可撤销并查集

众所周知，并查集不支持边的删除。但是，我们可以将加边操作逐步回退。为了做到这一点，我们只能使用按秩合并的并查集，然后用到一个栈来储存边（指的是连接两树根的边）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct edge{
    int x,y,w; //w记录秩是否改变
}st[N];
void join(int x,int y)
{
    int a=find(x),b=find(y);
    if(a!=b)
    {
        if(rk[a]>rk[b])
            swap(a,b);
        if(rk[a]==rk[b]) ++rk[b];
        fa[a]=b;
        st[++up]={a,b,rk[a]==rk[b]};
    }
    else
        st[++up]={0,0,0}; //即便无连接，也别忘了这一步
}
void withdraw()//回退上一次操作
{
    auto p=st[up--];
    if(p.x)
    {
        fa[p.x]=p.x;
        rk[p.y]-=p.w;
    }
}

种类并查集

(113条消息) 【转】种类并查集_panfengblog的博客-CSDN博客

一般的并查集，维护的是具有连通性、传递性的关系，例如亲戚的亲戚是亲戚。但是，有时候，我们要维护另一种关系：敌人的敌人是朋友。种类并查集就是为了解决这个问题而诞生的。

我们规定：处在一个集合中的元素彼此互为朋友。假如我们要维护这种关系：

BbFNwj.png

边(x,y)表示x与y互为敌人，那么我们可以开两倍空间，其中x+n与x互为敌人，x所在集合中的元素与x+n所在集合中的元素相互敌对（这个x+n不是真实存在的元素，它的作用是代表x的敌人，与x敌对的元素都要与之相连）。

对于一条边(x,y)，我们只需执行 join(x,y+n) 和 join(x+n,y) 。如果在加入边之前，发现find(x)==find(y)，说明x和y在一个集合中，也就是已经确立为朋友关系，那么当前所加的这条边就是矛盾边。（种类并查集是应用层面的，与之前的底层实现无关。）

显然，我们可以把这种方法应用到判断二分图上。另外，针对三个及以上的种类形成的环形敌对关系（A敌对B，B敌对C，C敌对A），也可以由此推广，这里不再赘述。

带删点并查集

（三）动态图

（四）树上连通块

参考：2018中国国家侯选队论文集

树上连通块问题学习笔记 - 123asdfghjkl 的博客 - 洛谷博客 (luogu.com.cn)

7、最短路

（一）Dijkstra

Dijkstra算法可求任一点到定点的最短路，适于有向图和无向图（对有向图有用的就一定对无向图有用），其边权不可为负（一条边都不行）。数组vis标记访问过的点，数组dis记录结果，一般初始化为无穷。dis[起点]要提前赋值，以保证在for循环中第一个目标点是起点。

对于稀疏图（即边的数量E远小于n*(n-1)），Dijkstra算法可以优化至(V+E)logV，称为堆优化。具体就是用优先队列，直接弹出待选结点中d[x]最小的点。普通二叉堆优化后的复杂度为O((V+E)logV)，而若使用斐波那契堆，由于压入操作为O(1)，可将复杂度优化至O(E+VlogV)（但是过程复杂，比赛中不使用）。在稀疏图中，使用二叉堆实现的 Dijkstra 算法较 Bellman-Ford 算法具有较大的效率优势；而在稠密图中，这时候使用暴力$O(n^2)$做法较二叉堆实现更优。

当边权均为一常数时，可用bfs搜寻；当边权为0和1时，可用双端队列+bfs搜寻。如果要还原路径，这时需要引入父点数组。由于除了起点外每个点都有唯一的父结点，这时所有路径便形成了一棵树，称最短路径树。在这棵树上，根节点到任意结点的路径最短。在保证1-u的路径最短下，u更换前驱，对其他节点毫无影响，从而产生不同的树。

当存在多个起点时（即多源最短路），可设置一“超级源点”，通过边权为0的边连接所有起点，则图上任一点到最近源点的距离即为到超级源点的距离，“超级汇点”同理。当某些点能通过特殊方式走到其他任何点时，可让它连接到一个虚点，这个虚点再连接到图中所有点。

在某一点到源点的路径长度最短的前提下，处理一些二级条件，我们需要在dis[to]==dis[index]+G[index][to]时：①使得路径上的点权和最小：当wg[to]>wg[index]+w[to]时更新wg[to]和fa[to]。（如果希望是希望点权和最小时使路径最短，那么我们把一二级条件互换即可）②使得路径上的最大点权最小：当wg[to]>max(wg[index],w[to])时更新wg[to]和fa[to]（与①不同，②的一二级条件不可互换）。③统计最短路数量：tot[to]+=tot[index]。④使得路径上的额外边权和最小：参考①即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(dis[to]>=dis[now]+w)
{
    if(dis[to]>dis[now]+w)
    {
        dis[to]=dis[now]+w;
        wg[to]=wg[now]+w[to];  //wg[x]为1~x的路径点权和
    	fa[to]=now;            //fa[x]为x在最短路径树上的父节点
    }
    else if(wg[to]>wg[index]+w[to])
    {
        wg[to]=wg[now]+w[to];
        fa[to]=now;
    }
}

一些最优路径问题并不是简单的权和最短，Dijkstra可以描述为在未标记的点中找到最优点，将其标记后优化其相邻点，这种优化/松弛是单调的，就像边权一样只可非负，以确保被已标记的点不可能再被优化更新。比如说，假设边权点权均为正数时，求1到任一点i的路径的最大的“最小点权/路径长度”、最小的“路径最大值最小值之差”等，这些值在点与点转移时，必然始终增加或减少（也就是转移边权恒大于0或小于0，具体值可以未知），而当边权恒正时求最小、边权恒负时求最大，我们就可以采用Dijkstra算法；若需边权可正求最大、边权可负求最小，则要用到spfa。

注意类似这样的问题不适于dijkstra算法：求两点所有路径的最小点权（或最大点权）。正如上文所说，该问题的状态在沿边转移时是递减的，dijkstra不能处理存在负边的最短路问题。不过，求两点所有路径的最小点权的最大值（或最大点权的最小值）倒是可以使用dijkstra算法，因为这类问题符合状态转移要求。

1
2
3
//以求最大点权最小值为例
auto t=pq.pop(); //弹出dp值最小的点
dp[to]=min(dp[to],max(dp[t],ar[to])); //更新最大点权最小值。dp可初始化为无穷大。

有向图中的最小环问题：枚举s=1-n，更新s所有的出边所连接的点v，设置dis[v]为边权，然后正常地跑一遍dijkstra，dis[s]就是经过s的最小环。

dijkstra算法的核心在于三角不等式$dis[to]≤dis[now]+w$，基于此，以下将介绍几种拓展应用。

差分约束

差分约束系统是一种特殊的N元一次不等式组。它包含N个变量$X_1$~$X_N$以及M个约束条件，每个约束条件都是由两个变量作差构成的，形如$x_i;-x_j;≤c_k$,其中$c_k$是常数(可以是非负数，也可以是负数)，1≤i, j≤N,1≤k≤M。我们要解决的问题就是：求一组解$x_1=a_1,x_2=a_2,…,x_N= a_N$，使所有约束条件都得到满足。

差分约束系统的每个约束条件$x_i;-x_j;≤c_k$，可以变形为$x_i;≤c_k;+x_j$，这与单源最短路径问题中的三角形不等式dist[y] ≤dist[x]+z非常相似。因此，可以把每个变量$x_i$看作有向图中的一个节点 i , 对于每个约束条件$x_i;-x_j;≤c_k$，从节点 j 向节点 i 连一条长度为Ck的有向边。

注意到如果{a1,a2, … ,an} 是一组解，那么对任意的常数△，{a1+△,a2+△, … ,an+△}也是一组解。这样如果我们想把一组含负数的解转换为正整数解，那么令上式中△为|最小的负数-1|即可。我们还可以设置一个虚点$x_0=0$并增设约束条件$x_i;-x_0;>0$，从而达到控制所有解的下限。如果差分约束系统中存在有向环，

不等号的方向可以自由选择，这要根据在具体问题中，求最短路还是求最长路更适合我们。注意不能在存在负边权的图中使用dijkstra算法求最短路（等价于不能在存在正边权的图中求最长路），也最好不要在非稀疏图中使用SPFA算法。另外，所求得的一组解只是针对一个连通块（底图连通，不含虚点）而言的，如果不止一个连通块，我们需要对每组解独立处理。

若$x_i-x_j≥k$表示$x_i$比$x_j$至少多 k ，$x_i-x_j≤k$表示$x_i$比$x_j$至少少 k 。我们将不等号统一方向，作由 j 向 i 的权值为k的有向边，如果差分约束系统中存在有向环，设环上边权和为 S，当求最短路时必须 S≥0，当求最长路时必须 S≤0。这意味着在非负边权图中，强连通分量对最长路的贡献只能为0，我们可以将图变成DAG图。

362. 区间 - AcWing题库

我们设$x_i$为0~i的前缀和，重点注意隐藏的约束条件。对于i>j，$x_i-x_j >=0$，且$x_j+1>=x_i$。

P3275 SCOI2011]糖果

同余最短路

同余最短路常用于解决这样一类问题：

有n个正整数$a_1,a_2,a_3,⋯ ,a_n$，设$x_1a_1+x_2a_2+…+x_na_n=k（x_1,x_2..x_n∈N）$ 。即 使用无限个$a_1,a_2,a_3,⋯ ,a_n$进行拼凑，然后对k的可能值进行各种询问（例如询问k在[ l , r ]区间内的可能值个数；询问k最大的无法拼凑的值；询问某个定值k能否被拼凑出……）（类似于超大完全背包）

算法思路

取其中一个正整数作为剩余系，例如取$a_1$，设$f(i)=min{k|k % a_1=i}$，其中$i=0,1,2..a_1-1$，$f(i)$即为令$k=x_2a_2+x_3a_3+…+x_na_n$且$k % a_1 =i$的最小的k。（虽然少了一项$x_1a_1$，但有和没有是一样的）（通俗点讲，就是选任意数量的$a_2到a_n$，凑成k使得$k%a_1=i$，$f(i)$即这个最小的k。**如果这个k不存在，则$f(i)=inf$**）。

由定义易知：$f((i+a_j)%a_1)=min{f(i)+a_j}$。其中$f(0)=0$。我们发现这可以转换为最短路的更新方程：$$f((i+a_j)%a_1)<=f(i)+a_j$$。

建图：显然共$V=a_1$个节点（从0到$a_1-1$），每个节点均有n条边，利用堆优化Dijkstra算法求最短路时间复杂度为$O(nVlogV)$。若n个正整数有重复值，则最好要去重，且为了使节点数更少，我们应当取最小的$a_i$作为剩余系。

求出所有的$f(i)$后：

（1）所有可拼凑出的值的集合即为${k|f(i)+t\cdot a_1,t∈N}$。由简单的数论知识可知，当$i,t$不同时，k唯一。若限制k<h，则可由n个正整数组成的所有不同数的总量为$\sum_{i=0}^{a_1-1}f(i)/a_1+1$，其中$f(i)!=inf$且$f(i)<=h$。（+1的情况是指d[i]本身，也就是一个a1都不取）

1
2
3
4
5
for(int i=0;i<P;++i) //P=a1
{
    if(d[i]!=inf && d[i]<=h)
        res+=(h-d[i])/P+1;
}

（2）最大的无法拼凑出的值为$\max{k|k = f(i)-a_1}$，若为−1则表示所有值均可拼凑出来（仅当$a_1=1$时），若为$inf-a_1$则表示不可拼凑出来的数有无穷个。例如有三个整数4,3,4，我们排序去重后取$a_1=3$，则$f(0)=0,f(1)=4,f(2)=8$，最大的不可拼凑的数即为$f(2)-3=5$。

1
2
3
4
5
6
//求最大
sum=0;
for(int i=0;i<t;i++)	sum=max(sum,d[i]-P);//P系数为1
//求最小
sum=inf;
for(int i=0;i<t;i++)	sum=min(sum,d[i]-(d[i]/P)*P);//P系数为d[i]/P

（3）对于一个定值k，若需要知道其具体的拼凑方案，则还需记录最短路的具体路径。

（4）判断一个数 x 能不能由$a_1,a_2,a_3,⋯ ,a_n$组成，因为 f 中存的是最小值，如果$x>=f[x%a_1]$，则一定能保证x由$f[x%a_1]$加上若干$a_1$得到，否则说明k=x无解。

P3403 跳楼机

P2371 国家集训队 墨墨的等式

P2662 牛场围栏 - 洛谷

遥远的旅途 (51nod.com) 图上超大完全背包

假设一条从0到n-1的路径长度为a，任取一条连接n-1的无向边，w为其长度，如果题目所述的长度恰好为T的路径存在，那么一定可以表示成：$T=a+k*2w;;(k∈N)$，即$T%2w=a%2w$。若k为0表示不需要在此边上重复走。理解这个“一定”：不管路径a走得多么复杂，我们只关心它对于2w的余数，这对所有a都是唯一的。

于是取P=2w为剩余系，设b为从起点到 i 的某一路径长度，我们令$dp[i][j]$表示使得b%P=j的最小的b，状态之间通过连接两点的无向边转移。初始化dp[0][0]=0，跑一遍Dijkstra就能处理出dp[n-1][0~p-1]。在点n-1上，若$T>=dp[n-1][T%P]$，说明 T 一定可以由记录在$dp[n-1][T%P]$上的路径a加上若干2w得到。

如此，我们使用了同余模型来优化极大的数据范围。这里之所以选取连接n-1的边，是因为一定可以保证这条边接入所有路径，所以按这来分析的话，我们还可以选连接起点0的一条边作为剩余系。

（二）Floyd

Floyd算法是解决任意两点间的最短路径的一种算法，是一种插点算法，可以正确处理有向图或带负权非回路的最短路径算法 同时也被用于计算有向图的传递闭包 Floyd时间复杂度为$O(N^3)$ ，复杂度为$O(N^2)$。

Floyd推理.png
状态表示 ： $f[k][i][j]$表示所有从i出发，最终走到j，只允许经过结点1到k的所有路径的最小值
阶段划分 ： 节点编号k的不同
转移方程 ： $f[k][i][j] = min(f[k][i][j], f[k - 1][i][k] + f[k - 1][k][j])$

初值$f[0][i][j]$为原图的邻接矩阵。

$f[k][i][j]$可以从$f[k-1][i][j]$转移来，表示i到j不经过k这个节点，也可以从$f[k-1][i][k]+f[k-1][k][j]$转移过来，表示经过k这个点。意思即$f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])$。通过滚动数组思想，我们约掉了第一维，进而表示成如今的Floyd。

（k作为第一维阶段状态，这也是它必须放在最外的原因）

任意两点最短路

Floyd可求任意两点间的最短路，代码简单，允许边权为负（但不能存在权和为负的环），可以作图的预处理。k, i, j都是对所有点的枚举，且第一个for为对k枚举。记录结果的二维数组d初始化为无穷大，若i,j有边，则设置d[i][j]**和dis[j][i]**为边长。memset(d,0x3f,sizeof(d))可使每个元素被初始化为1061109567（0x3f3f3f3f…），属于1e9级数，两个0x3f相加恰好比int_max小一点，因此是初始化“无穷大”的不错选择（多次调用Floyd时，最好摒弃这种做法）。注意，不要在两个0x3f3f3f3f相加后再加数值，可能会造成溢出。

使用一个path数组来记录i到j经过的某个中间点，也就是说，当d[i][j]>d[i][k]+d[k][j]时，设置path[i][j]=k，然后采用分治递归，便可还原路径。注意，在有多条等长路径时，若采用“>”，所记录路径经过的顶点/边最少；若采用“≥”，所记录路径经过的顶点/边最多。如果两点p,q在i到j所记录的最短路径上，那么p到q的路径也一定记录在这条路径中。还可以设置path[i][j]为自i向j出发的下一个点，初始化path[i][j]=j（对无向图还需初始化path[j][i]=i），当dis[i][j]>dis[i][k]+dis[k][j]时，设置path[i][j]=path[i][k]，打印时循环输出即可。

1
2
3
4
5
6
7
8
void func(int a,int b)
{
    if(!pt[a][b])
        return;
    func(pt[a][b],b);
    cout<<pt[a][b])<<" ";
    func(a,pt[a][b]);
}

对于点比较多的稀疏图，一个直观的想法就是，对每个点执行一次Dijkstra算法来求出任意两点最短路，复杂度为O(nmlogn)，然而Dijkstra算法不能处理含负边权的图。1977年，Donald B.Johnson提出了对所有的边权进行”re-weight”的算法，使得所有边权非负进而可以使用Dijkstra算法进行最短路的计算。

最小环问题

由上述可知，当外层的 k 刚循环到点 t 时，点t一定只存在于所有当前记录的path的端点上，而不出现在任何path的途中，也就是说，当前所有$dis[i][j]$表示由i向j出发不经过点集t~n的最短路。此时$dis[i][j]+dis[i][k]+dis[k][j]$构成了一个经过i,j,k的最小环，因此可在floyd的过程中求出(无向图)最小环。

传递闭包

在交际网络中，给定若干个元素和若干对二元关系，且关系具有传递性。我们可以使用邻接矩阵来表示变量间的关系，比如说当$g[i][j]=true$代表 i 和 j 有关系，然后，我们可以使用Floyd算法解决传递闭包问题。

1
2
3
4
for(k)
	for(i)
		for(j)
			g[i][j]|=g[i][k]&g[k][j];

再比如说当$g[i][j]=true$代表 i<j ，这时我们有：

1
2
矛盾:        g[i][j]==1&&g[j][i]==1  => a>b && b>a
不能确定大小： g[i][j]==0&&g[j][i]==0  => a?b && b?a

如果一个描述大小关系的传递闭包中没有矛盾和歧义，那么总会呈现例如这种形式：

1
2
3
4
5
//  A B C D
//A 0 1 1 1
//B 0 0 1 0
//C 0 0 0 0
//D 0 1 1 0

可见每一行的1的数量都不相同，假设元素x所在行的1的数量为k，那么在将所有元素按从大到小的顺序排列后，x就排在第k个，且整个顺序是一定确定的。

我们可以再进一步用 bitset 优化，复杂度可以到$O(n^3/32)$

1
2
3
4
// std::bitset<SIZE> g[SIZE];
for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    if (g[i][k]) g[i] = g[i] | g[k]; //表示g[i]可以继承g[k]的所有关系

矩阵快速幂

（数学水平不足，待更新）345. 牛站

点权排序

我们已经知道，当外层的k刚循环到t时，点t一定只存在于当前所有所记录的最短路径的端点上（注意只是当前的最短路径，不是最终）。点的遍历顺序并不影响Floyd算法，于是，如果将点1~n按点权大小进行排序，那么在所有最终最短路径的生成过程中，一定能保证路径最大/最小点权的单调性。详细地讲，对固定的两点$i,j$，其当前最短路径$f[k][i][j]$的最大/最小点权一定只来自w[i],w[j],w[k]，其中w[i], w[j]是常数，故而路径点权最值是单调变化的。

既然保证了点权最值单调，那么就可以维护一些与点权和边权都相关的值。比如说：

（1）求任意指定的两点路径中，最大点权不超过k的最短路径。点权排序后，任意两点的最短路径在生成过程中，最大点权递增而最短路径递减，我们可以把所有询问，按k的大小排序，在Floyd算法的过程中顺便解决，或者开二维map[N][N]，用mp[i][j][w]记录当$i,j$的路径最大点权为w时的最短路径，这样在每次最短路更新时，$w=max(w[i],w[j],w[k])$，直接设置$mp[i][j][w]=d[i][j]$即可。注意一开始如果$i,j$有边，要么初始化mp[i][j]，或者在更新值时采用“≥”。

P1119 灾后重建

（2）求任意指定的两点路径中，最大点权乘以最大边权的最小值。对于固定的两点$i,j$，在最短路径生成的过程中，为了使乘积最小，当最大点权递增时，我们更新最大边权的最小值（相当于剔除掉最大边权跟着递增的没有贡献意义的部分），这样就使得路径$i,j$在此过程中最大点权递增而最大边权递减，每次更新时维护最小乘积res[i][j]即可。注意一开始如果$i,j$有边，要么初始化res[i][j]，或者在更新值时采用“≥”。

阿强的路 (nowcoder.com)

（三）Bellman-Ford

Bellman-Ford 算法是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。它的代码实现极为简单——对所有的边松弛n-1次。

1
2
3
4
for(k = 1; k <= n - 1; k++)
    for(i = 1; i <= m; i++)
        if(dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];

此后可再对所有边尝试一次松弛，倘若成功松弛了某条边，说明存在负环。

负环的定义是：一条边权之和为负数的回路。最短路下的负环和最长路下的正环都会导致问题无解。另外，对于涉及“环上绝对值最小”的问题（如01分数规划），也可以考虑对负环性质的运用。

SPFA

很多时候我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。这种优化手段（在国内）被称作SPFA算法。

必须说明的是，SPFA算法虽然跑得更快，但其最坏情况下的时间复杂度为O(nm)，没有负权边时最好使用 Dijkstra 算法。在有负权边且题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman-Ford 算法无法通过的数据范围。

关于SPFA的两种优化：

  • LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
  • SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。

我们可以把LLL和SLF结合到一起：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int vis[maxn],dis[maxn];
vector<pair<int,int> > G[maxn]; //邻接表
void spfa(int st)
{
    deque<int> q;
    q.push_back(st);
    dis[st]=0;
    long long sum=0,num=1;
    while(!q.empty())
    {
        int t=q.front();
        while(dis[t]*num>sum) //LLL优化
        {
            q.pop_front();
            q.push_back(t);
            t=q.front();
        }
        vis[t]=0;
        q.pop_front();
        --num;
        sum-=dis[t];
        for(auto i:G[t])
        {
            if(dis[i.first]>dis[t]+i.second)
            {
                dis[i.first]=dis[t]+i.second;
                if(!vis[i.first])
                {
                    if(!q.empty() && dis[i.first]>dis[q.front()]) //SLF优化
                        q.push_back(i.first);
                    else   
                        q.push_front(i.first);
                    ++num;
                    sum+=dis[i.first];
                    vis[i.first]=1;
                }
            }
        }
    }
}

其他优化手段：spfa的魔改方法 - ETO组织成员 - 博客园 (cnblogs.com)

SPFA可以通过两种方式来判断负环：（1）一个点是否入队达到n次（2）起点到某点的最短路径边数是否达到n。需要注意的是，以S点为源点跑 SPFA 算法时，如果没有给出存在负环的结果，只能说明从S点出发不能抵达一个负环，而不能说明图上不存在负环。因此如果需要判断整个图上是否存在负环，最严谨的做法是执行 Bellman-Ford 算法，或者建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行SPFA算法。

虽然是介绍SPFA的章节，但我们却要着重地讨论“如何不用SPFA”。考虑在哪些情况下，可以绕开SPFA解决含负边权的最短路问题。

SCC缩点

众所周知，将有向图中的强连通分量（SCC）缩点后，便将图转换为了有向无环图。在DAG上，无论进行拓扑排序+DP还是记忆化搜索，都有十分理想的时间复杂度。如果一个强连通分量对所有穿过它的图上路径的贡献是确定的，我们就能将其缩为DAG上的一点。此类问题一般允许经过重复点。

P3387 缩点 SCC对经过它的路径的贡献，就是每个SCC中的点权总和。

342. 道路与航线

题意描述：一幅由有向边和无向边构成的图，其中无向边权为正数，有向边权可负，保证任何环中都不含有向边，求从起点S到任一点的最短路。

如果我们将所有的无向边连通块缩成一个点（把有向边视作断开作dfs即可，用不到Tarjan），那么这个图就变成了一个DAG。此时我们就可以对这个图进行拓扑排序了，然后再根据拓扑序进行递推，最终就可以求出到达每个点的最短路径。由于无向边权为正，每个缩点内部的最短路我们可以直接用dijkstra算出。

（直到起点在某次djjkstra算法从堆中被弹出前，所有点的dis值都是inf。）

在这里插入图片描述

NOIP2009 提高组] 最优贸易 尽管这道题的正解是双向SPFA，但我们有更多时间复杂度更优秀的解法。

只需分别求出起点到任一点的最大路径点权和终点到任一点的最小路径点权即可，然而这两者都无法采用djjkstra算法得出（根据定义仔细想想）。缩为DAG后，比如在求路径最大点权时，每个SCC的贡献就是自身的最大点权。

在DAG图中找最长路，我们可以在拓扑排序后，遍历每个点，沿着其出边松弛其他点的dp值，或者更直观地，我们建立反图，从各个终点进行记忆化搜索，（建立反图是因为记忆化搜索自底向上，更适合表示 i 到 n 的最长路），复杂度为边数。

值得一提的是，所有路径规划算法本质都是在图上进行动态规划，每种算法有对应的状态转移方程（dis数组实际就是起到dp数组的作用），并利用边进行状态转移。不过动态规划问题一般都是基于DAG图（即无后效性），当存在环且不是负环时（换句话说，不会出现沿着一个环一直刷小/刷大状态值），用spfa算法一遍遍地沿每条边松弛，就能得到每个点的dp值。例如在“通信线路”中，设dp[i][p]表示从1到i的路径第p大的边的最小值，则对于权值为z的边x->y，有$dp[y][p]=min(max(dp[x][p],z) ,dp[x][p-1])$,显然沿着一个环（边权为正）不会使dp[y][p]一直减小（包括无向边的来回），因此可以使用SPFA算法。

（四）分层图

基础运用——

分层图是指有很多个平行的图，各个平行的图之间有特殊的连接边。分层图只是建图时有区别，但诸如跑最短路板子都是一样的，只要有合适的建图方法，那么问题就很简单了。

为了更好地配合dijkstra等算法，一般的建图方式是把第x（0~k-1）层的i点表示为$i+xn$，其中最后一层$（i+kn）$为终点层或虚层。分层图的点数近似kn，边数近似km，以此来计算时间复杂度。

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=m;++i)
{
	int x,y,z;//有向边的起点、终点、边权
	cin>>x>>y>>z;
	for(int j=0;j<=k;++j)//在每一层图上建立相同的边
	{
		G[x+j*n].push_back({y+j*n,z});
		G[y+j*n].push_back({x+j*n,z});
	}
}

分层图的几种使用场景：

1、 有k套不同边集建立在同一点集上，允许在某点消耗代价切换到另一边集上移动。有多种情况。

小雨坐地铁 (nowcoder.com) 换乘问题。可以将每个集合内的边建成一张图，再建立第k+1个图，是一个虚层，这个虚层的i点作为中转站，连接了前面k层所有的i点（双向边，指向虚层的边权为0），从而不需要去把每一层的同一点两两连边。如果任意一层图的某一位点$i$，切换到第$t$层的$i_t$需消耗x，可令虚层指向$i_t$的边权为x。这样任意层图就可以通过虚层转移到另一层图中。

Rinne Loves Dynamic Graph (nowcoder.com) 边权变化具有周期性，为每套边权建立分层图。

Problem - 7145 (hdu.edu.cn) 入边的不同，决定了每个点接下来的出边。此题的有向图中如果由A型边到一点，接下来可走A/B型边，如果由B型边到一点，接下来只能走A型边，我们建立两层图，第一层的点只接受A型入边，第二层的点只接受B型入边。（但是我不太理解这道题的时间复杂度）

其他例子：

在迷宫中有若干扇门，还有若干把钥匙处在不同位置，只要拿到一把，便能打开所有的门，求从起点到终点的最短路。

建立两层图，一层有门，一层无门，开始从有门的图出发，可通过钥匙所在的点达到令一层。我们延伸这道题：如果有s种门和s种钥匙，那么需要建立2^s张图G(a1,a2,…,as)，ai只取01，表示在该层图中第s种门开不开。

2、 有k个机会使得走当前此边不花费代价或花费特殊的代价，可以建立k张相同的该图，对于边i-j，让上一层的i指向下一层的j，其代价是0或是特殊的值。每向下走一层，就代表用了一次机会，使得当前的路花费为0，最多可以走k次（注意如果这k次不必用完的话，每一层的终点可能更新答案）。如JLOI2011] 飞行路线

3、 有k个机会逆向走动，我们可以建k张相同的该图，将每层图之间有边的两个点用的逆向的边连接。每向下走一层，就代表用了一次机会逆向走了一次，最多可以走k次。

分层图与动态规划——

经典题：NOIP2017 提高组] 逛公园

建立k+1张分层图，每一层图完全相同。称第0层的起点为始祖源点，第t层的所有点都代表了从祖源点到这里要多走t距离。

设dp[i]为从祖源点到任意层$i$点的路径数，我们的目标就是统计$dp[n]+ dp[n+n]+…+dp[n+kn]$。
在正式开始前，设dis[i]为i到n的最短路，我们建立反图，做一次dijkstra算法。1≤i≤n，dis[i]是一个全局量，跟在哪层无关。

假设现在在第0层，设连接$x$到$y$的有向边边长$w$，若$dis[y]-dis[x]<w$，说明沿此边多走了$c=w-(dis[y]-dis[x])$，于是我们断开本层x-y，建立一条从$x$到$y+cn$的有向边（也不必物理断开，只要强制优先向下走就行了）。把第0层换作第t层也一样，我们建立一条从$x$到$y+(t+c)n$的有向边。
现在，我们从祖源点出发沿着有向边自由走动，以任一层的n为终点。显然，路径上不会出现环（成环之前一定会向下移动，0环除外）。也就是说这些自由移动的路径形成了有向无环图，我们可以进行记忆化搜索或拓扑排序DP。*例如对记忆化搜索而言，总复杂度为$O(KM)$。没有必要用SPFA进行DAG动态规划。*

本题还需要对零环进行判断。事先说明，前面之所以选用i到n的最短路，是因为所有合法路径的终点是n，如果dis[i]=inf，说明走到i就到不了终点了，因此我们不向i移动（选用1到i的最短路也可以正确转移状态，但是会在不合法的路上浪费时间）。至于0环，我们在记忆化搜索时标记正处在递归状态中的节点，如果dfs到一个还未退出递归的节点，说明“DAG图”上出现了环，这个环一定是所求的零环。

还有一个问题，我们真的需要建立这K+1层图吗？注意到每层图的边集完全相同，因此我们用$dp[k][i]$来表达第k层的i点，在原始图上进行动态规划。

有了这种分层图DP的思想后，看待很多在有向图（有环）上的动态规划时，就不难以理解了。

340. 通信线路 - AcWing题库 （尝试用动态规划）

8、二分图