树的直径&基环树&单调队列
树的直径
定义:树中最远的两个节点之间的距离被称为树的直径。
怎么求呢?有两种官方的算法(不要问官方指谁我也不晓得):
1.两次搜索。首先任选一个点,从它开始搜索,找到离它最远的节点x。然后从x开始搜索,找到离x最远的点y,那 么e(x, y)的长度就是树的直径。时间复杂度为o(n)。
2.树形dp。这种其实更好写。我们可以对于某个节点x,分别求出经过它的最长链的长度。怎么求呢?首先,枚举x 所连接的k个节点yi(i ∈[1,k]),都求出以yi为根的子树最大深度d[yi]。那么,经过x的最长链长度f[x] = max{d[yi] + e(x, yi)}(i ∈[1, k])。~好理解吧~那么这个算法的复杂度就是o(n)。
实际上,搜索求直径的复杂度为o(2n),是树形dp的两倍。不过影响不大,并且搜索可以节省内存。搜索美滋滋。
//搜索求解 int mmax, pos; void dfs(int u, int pre, int w){ if(w >= mmax){ mmax = w; pos = u; } int v; for(int i = head[u]; ~i; i = e[i].next){ v = e[i].to; if(v != pre) dfs(v, u, w + e[i].dis); } } //main函数中 dfs(1, 0, 0); dfs(pos, 0, 0);
//dp求解 int d[maxn], f[maxn], ans; bool vis[maxn]; void dp(int u){ vis[u] = true; int v; for(int i = head[u]; ~i; i = e[i].next){ v = e[i].to; if(!vis[v]){ dp(v); ans = max(ans, d[u] + d[y] + e[i].dis); d[u] = max(d[u], d[y] + e[i].dis); } } } //main函数中 dp(1);
我们首先证明一个定理:
给定一棵树,对于它的任一直径,若取其几何意义上的中点,叫做这条直径的中点。那么, 一棵树的所有直径的中点必定是同一点。
证明:
显然,当这棵树只有一条直径时,定理成立。但很多情况下一棵树不止一条直径。但所有直径必定都经过同一点。为 什么呢?(下面证明的过程中有关长度与距离之类的量都为几何意义上的量)
假设有两条直径不经过同一点。设两条直径分别有一点a,b,并且a能够在不经过这两条直径上的边的情况下到达b。 那么这两个节点就将所在的直径分成了两段。我们取每条直径上较长的那段,加上a和b之间的长度,显然大于原来 的直径长度。
那么任意两条直径必定会相交于一点。现在再假设有两条直径满足它们的中点a,b不是同一点。显然对于中点来说, 它将其所在直径分成了相同长度的两段。不妨设有一条不经过直径的路径连接a和另一条直径上的c点,那么:a所在 直径长度的1/2 + e(a,c) + e(b,c) + b所在直径长度的1/2 ≥ 任意一条直径的长度 = a所在直径长度的1/2 + b所在直径 长度的1/2,这样就存在一条新的路径,其长度大于原来的直径,这有悖直径定义。
证毕。
(φ皿φ)证出来了~
回到直径这道题,我们可以先随便求一条直径出来,然后设法搞出它的中点(直径长度/2的位置)。现在有两种情况:
1.(软柿子)中点就是树的某个节点。我们可以直接以这个点为根进行计算。
2.中点在树的某条边上。酱紫的话就把这条边扔了,在剩下的两棵子树上计算。
怎么计算呢?
第一种情况,由于从根节点可以连接出许多棵子树。我们取出深度最大的三棵子树a,b,c,并用d[x]表示x子树的最大 深度。
1.d[a] > d[b] > d[c]。显然直径会经过a子树和b子树。然后我们递归,在a子树和b子树的根上进行相同计算,算出直 径必然经过的边。
2.d[a] > d[b] = d[c]。那么只需在a子树的根上进行相同计算即可。
3.d[a] = d[b] = d[c]。那么没有被所有直径经过的边。
如法炮制,对于第二种情况,我们只需在去掉边之后的两颗子树上分别进行上述操作即可。
总结与拓展:
对于树的直径问题,我们会有两种做法:搜索与dp,两者复杂度相似。在看过例题“直径”之后我们可以证明出了一条 定理:一棵树的所有直径必定以同一点为中点。实际上,在做树上问题,特别是树的直径时,证明是少不了的。当然看上去正确的定理水一水也就过了。然而,树的直径通常不会单独在一道题里出现,它经常伴随着其它的算法, 如“直径”中最后计算时整的什么鬼算法,还有经常会和树的直径一起用的二分答案。多练吧~
基环树
顾名思义,基环树就是基于环的树。
对于一棵树,若它有n个点,则一定有n-1条边。而如果在其之上添加一条边,那么就会形成一个环(好理解吧~溜 ~)。加了环之后,这个什么鬼就叫基环树。
基环树的题目并不多,但是对于大部分的题,我们可以很容易判断出它的图是否为基环树。通常会有两种特征:
1.点数为n,边数也为n
2.且每条边都至少连出去一条边(出度≥0)
举个例子:
eg.1
很明显的基环树
eg.2
简直在告诉我们它是基环树
通过这两道考试的原题你可以看出,基环树是多么重要的一个乱七八糟的结构
那么,对于基环树的问题,我们怎么解决呢?(这里直接讲刚才的例题因为没有官方算法)
第一题就先不看了
我们看岛屿这题:
这题显然是有不只一棵基环树,因此我们可以对每棵树都求一下可以走过的最大长度。
那么,这就有点类似于求树的直径了。那么我们引入一个新的概念(不是官方的):基环树的直径——基环树上最长 的简单路径(不自交的路径)。其实也是最远两点之间的距离(这样会比较高端)。
如何求呢?对于一棵基环树,它的直径会有两种情况:
1.去掉环上所有边之后的某棵子树的直径。
2.环上分别以两点为根的两棵子树的直径加上它们环上的距离,这个环上距离可以是逆时针的,也可以是顺时针的。
所以,想要ac岛屿这道题,我们只需要求出每棵基环树的直径,再累加起来就是答案了。
怎么求呢?——为了逃避第二种情况我们先求解第一种情况。
显然,我们可以首先dfs一次图,找出图中的环。然后枚举环上每个点,分别求出以这个点为根的子树的直径d[i]。那 么答案就累加上直径。
第二种情况。我们枚举环上每个点,分别求出以之为根的子树的最大深度d[i]。那么答案就累加上max{d[i] + d[j] + dist(i, j)},其中i,j∈环,dist(i, j)表示i和j的环上距离(顺时针和逆时针的较大者)。怎么算dist呢?可以用一个熟悉的 技巧——拆环(合并石子里面的),即把环从一个点断开并拉成一条链,再把这条链复制一份塞到后面去。然后枚举这 条链上的点,算出其前缀和sum[x],那么dist(i, j) = max(sum[i] - sum[j], sum[j + lenth] - sum[i])。其中lenth是 环的长度。但不用这么算,因为枚举得到点j+lenth。所以,ans += {d[i] + d[j] + sum[i] - sum[j]}。那么这个算法 就是o(n²)。然而数据范围是10^6,这种算法显然过不了。那就不做了。不过优化是有的。怎么优化呢?单调队列牛 批!
所以我们先学一下单调队列
单调队列
何为单调队列?答:单调的队列。(啪!)
单调队列是用来找区间最值用的又一个乱七八糟的数据结构。可以stl里面的双端队列deque来实现,但那种方式的 开销不如手写的少。怎么找最值呢?我们来看看单调队列通常用来解决的问题:
给定一个数列a[n],求出区间[i - k, i]中的最大值,其中i∈[1, n], k为常数。
我们首先开一个数组,并用两个int变量作为它的首尾l和r。我们枚举数列的每个下标。当枚举到i下标时,我们将a[i] 入队,并判断一下a[i]是否大于之前队列的队尾值。若是大于,那就有悖单调队列的定义(单调的队列),那就不停将 队尾出队,直到q[r] >= a[i]为止。这样就维护了队列的单调性。再看,根据题意,我们只需要计算长度为k + 1的区 间。所以,我们再判断一下:若l < r - k,那么将l加到r - k为止。那么,一个单调队列就维护好了。
给出代码:
#include <iostream> #define maxn 1000000 + 5 using namespace std; int a[maxn], n, k; int list[maxn], l, r; int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); } l = r = 0; for(int i = 1; i <= n; i++){ while(l <= r && list[r] < a[i]) r--; list[++r] = a[i]; while(l <= r && l < r - k) l++; printf("%d\n", list[l]); } return 0; }
sample in: 7 4 7 6 8 12 9 10 3
最小值的求法也是类似的~
封坟————————————
挖~
然后我们回到岛屿这题。看到之前得出的表达式:ans += {d[i] + d[j] + sum[i] - sum[j]}。其中,我们只需枚举i∈[1, n],然后对于已经枚举过的j∈[1, i - 1],我们可以用单调队列来维护这段区间的max(d[j] - sum[j])。然后,因为我 们复制了环,所以当i > lenth时,我们只需在[i - lenth + 1, i - 1]里面找最大值即可。这些就巧妙地对应了刚才单调 队列里面的所有操作,因此整个算法的复杂度为o(n)。快不快?
总结:
对于基环树的问题,我们一般的做法是先处理环上部分,再处理以环上节点为根的每棵子树。但这也不是普遍适用 的,比如:
就是这货,它的解法是从一点开始贪心,找到环时再特判一下去最优值,根本不是上面所的一般情况,所以这里不做 过多讨论。其实是没ac
end