欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

树的直径&基环树&单调队列

程序员文章站 2022-04-14 17:03:16
树的直径 定义:树中最远的两个节点之间的距离被称为树的直径。 怎么求呢?有两种官方的算法(不要问官方指谁我也不晓得): 1.两次搜索。首先任选一个点,从它开始搜索,找到离它最远的节点x。然后从x开始搜索,找到离x最远的点y,那 么E(x, y)的长度就是树的直径。时间复杂度为O(n)。 2.树形dp ......

树的直径

定义:树中最远的两个节点之间的距离被称为树的直径。 

怎么求呢?有两种官方的算法(不要问官方指谁我也不晓得)

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