树上倍增

Nannan Lv5
  2023-08-15 21:11 2023-08-15 21:11 Created   2024-09-30 19:50:51 2024-09-30 19:50:51 Updated      

树上倍增

一、一点理解

最近遇到几个关于树上倍增问题。本人太菜，有时候想不到用倍增，这里做个总结。

树上倍增核心就是：，含义是向上跳步到的位置，然后用进行转移。

树上倍增常见应用就是：快速幂、线性（RMQ问题）、树（LCA问题）。

那么我们怎么去理解这个树上倍增呢？

由：介个大佬写的博客 引发的思考。可以将倍增理解为【树上二分】。

对于一颗树，我们需要先预处理出”二分”的位置。

怎么说呢，未知上界的二分可以考虑倍增。

一个快捷的对取方法：

1
int logn = 31 - __builtin_clz(n);

二、比如以下几个题：

先说一个常见模型：

给出一个长度为的环和一个常数，每次会从第个点跳到第个点，总共跳次，每个点都有一个权值，求次跳跃的权值和(结果对取模。

思路：首先是级别的，显然不能直接暴力跳了。考虑优化，思考我们上面说的【未知上界的二分考虑倍增】。那么我们需要进行预处理，考虑一个点跳步能到的位置，以及跳步的权值和。

那么对于跳步：

1
2
3
4
5
6
7
8
9
10
11
12
int cnt = 0;
int curx = 1;
while(m)
{
    if(m&1)
    {
        ans = (ans+sum[curx][cnt])%mod;
        curx = p[curx][cnt];
	}
    m>>=1;
    cnt++;
}

例题1：1010 Calculate

题意：给你一个个点条边的图，一个点只能通过唯一一条边到另一个点。

一开始的值为,当到达点的时候，值变为。

给你个询问，问你从点出发，走步,一开始的值是，问走步之后的值是多少。

思路：当时看到这个题，由于的范围是太大了，直接暴力走会寄。我就想到，对于个点条边，那必然是有环的，然后想要怎么处理这个环。最初的想法是，对于每个点，处理出可以走的路径，有环的话把环展成链，因为一旦进入环就走不出去了，就会一直循环，我们对循环节进行处理，可以解决时间复杂度的问题。但是！这样显然是错的，首先，因为每一次移动之后值是会变的，移动一个循环的增量太复杂。。根本无非求解。

转化思路！！再看看题目！当前在点，我们取往后跳，每次能够跳到的点是唯一的，也就是有唯一父子关系。那么考虑倍增。先预处理出每个点跳步的贡献，因为是的复杂度，我们不要考虑环了，暴力跳就行了。

预处理的时候把初始为当前点跳步能到达的点。

：往上跳步能到达的点。

：往上跳步的值，当然分开算。

总结：当一个点能跳到的下一个点是唯一确定的，且步数很大的时候，我们可以考虑用倍增。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int mod = 1e9+7;

struct ty
{
	ll k,b;
}f[N][32];
ll p[N][32],k[N],b[N];

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,q;
		cin>>n>>q;
		for(int i = 1;i<=n;i++)
			cin>>k[i];
		for(int i = 1;i<=n;i++)
			cin>>b[i];
		for(int i = 1;i<=n;i++)
		{
			cin>>p[i][0];
			f[i][0].k = k[p[i][0]];
			f[i][0].b = b[p[i][0]];
		}

		for(int j = 1;j<=30;j++)
		{
			for(int i = 1;i<=n;i++)
			{
				p[i][j] = p[p[i][j-1]][j-1];
				f[i][j].k = f[i][j-1].k*f[p[i][j-1]][j-1].k%mod;
				f[i][j].b = (f[i][j-1].b*f[p[i][j-1]][j-1].k%mod+f[p[i][j-1]][j-1].b)%mod;
			}
		}
		ll kk = 1,bb = 0;
		ll x,l,y,cnt = 0;
		for(int i = 1;i<=q;i++)
		{
			kk = 1,bb = 0;
			cnt = 0;
			cin>>x>>l>>y;
			while(l)
			{
				if(l&1)
				{
					kk = kk*f[x][cnt].k%mod;
					bb = (bb*f[x][cnt].k%mod+f[x][cnt].b)%mod;
					x = p[x][cnt];
				}
				l>>=1;
				cnt++;
			}
			cout<<(kk*y%mod+bb)%mod<<"\n";
		}
	}
	return 0;
}

例题2：H.Life is a Game

题意：给你个点条边的无向图。每个点有点权，每条边也有边权。我们有一个初始能量值，每经过一个点，可以获得当前点的点权，但是要经过一条边，需要我们当前的能力值大于这个边的边权才能走。给你起点和初始能量值，问你能量值最大可以是多少？

思路：重构树+树上倍增

由于有边权的限制，当能量值大于当前边权才能走。那么对于一条简单路径，限制我们的是这条路径上的最大值。我们考虑最优策略，如果有多条路，肯定走最大值越小的路。那么想让最大值最小，考虑重构最小生成树。重构完之后，任意两点的就是这个路径上的最大值了。

我一开始的思路是：从当前给出的节点往上走，如果当前的值大于等于限制，我们就可以获得这个子树的所有点的权值。但是了。考虑最坏的情况，二叉树退化成链，这样的话，就是跑的暴力了，肯定是会的。那怎么办呢？

因为我们建的是重构树，是个大根堆，考虑预处理出每个点往上跳步的花费**(预处理出”二分”位置)**。这里花费是指【要跳到的节点的限制-当前节点子树的权值和】。也就是，当前已经可以走到这里了，那么以当前节点为根的子树的权值我都可以得到了，用我要跳到的点的限制-当前获得的，就是我们的额外的花费。我们用这个花费和去比，如果小就可以往上跳，直到不能跳了为止。那么答案就是你能跳到的点的权值和+初始值。

总结：这个题也是，我要往上跳，可是我不知道能跳到哪里。如果暴力跳肯定,思考上面说的【未知上界的二分考虑倍增】，这样优化到级别的了。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long 
using namespace std;
typedef long long ll;
const int N = 4e5+10, M = 5e5+10;
const int LOGN = 20;
struct Node
{
	int x,y,v;
}a[M+1];

int n,m,q,now,val[N],dep[N],faa[N];
vector<int>e[N];
int ls[N],rs[N];
int sum[N];
int f[N][LOGN+2],cost[N][LOGN+2];
int c[N];//以i为根的子树的权值和

//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
	int fa[N];
	void init(int x) {for(int i = 1;i<=x;i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {
		int u = find(x), v = find(y);
		if(u == v) return;
		fa[u] = v;
	}
}dsu;
/////////////////////////Kruskal////////////////////////////////////

void kruskalRebuildTree()
{
	dsu.init(2*n-1);
	sort(a+1, a+1+m, [](const Node& x, const Node& y) {
		return x.v < y.v;//重构最小生成树
	});
	now = n;
	for(int i = 1;i<=m;i++) {
		ll u = dsu.find(a[i].x), v = dsu.find(a[i].y), w = a[i].v;
		if(u != v) {
			val[++now] = w;
			c[now] = c[u]+c[v];
			cost[u][0] = val[now] - c[u];
			cost[v][0] = val[now] - c[v];
			f[u][0] = f[v][0] = now;
			dsu.merge(u, now);
			dsu.merge(v, now);
			ls[now] = u;
			rs[now] = v;
		}
	}
}


////////////////////////////Main///////////////////////////////////
signed main()
{
	ios::sync_with_stdio(false);	cin.tie(nullptr);cout.tie(nullptr);

	cin>>n>>m>>q;
	for(int i = 1;i<=n;i++)cin>>c[i];
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	kruskalRebuildTree();
	
	for(int j = 1;j<=LOGN;j++)
	{
		for(int u = 1;u<=now;u++)
		{
			f[u][j] = f[f[u][j-1]][j-1];
			cost[u][j] = max(cost[u][j-1],cost[f[u][j-1]][j-1]);
		}
	}
	while(q--)
	{
		int x, k;
		cin>>x>>k;
		
		for(int j = LOGN;j>=0;j--)
		{
			if(cost[x][j]<=k&&f[x][j])x = f[x][j];
		} 
		cout<<c[x]+k<<"\n";
	}
		
	return 0;
}

  • Title: 树上倍增
  • Author: Nannan
  • Created at : 2023-08-15 21:11:00
  • Updated at : 2024-09-30 19:50:51
  • Link: https://redefine.ohevan.com/2023/08/15/六(二)、树上倍增/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
树上倍增
  1. 树上倍增
    1. 一、一点理解
    2. 二、比如以下几个题：
      1. 例题1：1010 Calculate
      2. 例题2：H.Life is a Game