首页 > 其他分享 >「树链剖分」 学习笔记

「树链剖分」 学习笔记

时间：2024-04-15 12:44:21浏览次数：36  
标签：剖分 int top tu 笔记 树链 tv tid son

一，树链剖分的思想与概述

正如其名，树链剖分用于将树剖分成若干条链的形式，以维护树上路径的信息，其中剖分出的链有多种形式，最常见的是重链，还有长链或更多其它的链。

其中剖分出的链为重链时，就引出了下文的主角「重链剖分」。

重链剖分能保证划分出的每条重链上的节点 DFS 序连续，因此可以用一些维护序列的数据结构（如线段树，树状数组等）来维护树上路径的信息。

没学过线段树的出门左转题库搜索线段树模板 1。

二，重链剖分

  1. 定义

  • 重儿子：表示其子节点中子树大小最大的节点。（多个点大小同时最大取任意一个）

  • 轻儿子：除重儿子外的其它所有子节点。

  • 重边：非叶子结点到它的重儿子的边。

  • 轻边：非叶子结点到它的轻儿子的边。

  • 重链：若干条首尾连接的重边构成的链。

  • 链首：每条重链中深度最小的点。

  • 重边优先遍历：DFS 遍历树时，优先遍历重边，其余同深度优先遍历。

其中，我们把把落单的结点也当作一条重链，那么整棵树就会被剖分成若干条重链。

如图：

  1. 实现

分两个 DFS，第一个 DFS 求出所有节点的 \(fa\)（父），\(dep\)（深度），\(size\)（子树大小），\(son\)（重儿子）。第二个 DFS 求出所有节点的 \(tid\)（在重边优先遍历时的 DFS 序），\(top\)（每个点所在重链的链首）。

我们钦定根节点的深度为 0。

\(1\) 号 DFS：

int fa[N], sz[N], dep[N], son[N];//上文所提的 4 个数组
void dfs1(int u, int f){
	sz[u] = 1;
	for (int i = pre[u]; i; i = e[i].next){//这里用的是链式前向星，也可以用 vector，看个人习惯
		int v = e[i].to;
		if (v == f) continue;//fa 和自己之间来回走（死循环）
		fa[v] = u;//记录 fa
		dep[v] = dep[u] + 1;//记录 dep
		dfs1(v, u);//DFS 得到 v 的 size
		sz[u] += sz[v];//记录 u 的 size
		if (sz[v] > sz[son[u]]) son[u] = v;//如果 v 的 size 大于原本 u 的重儿子的 size，更新 u 的重儿子为 v，其中 son 数组初始化为 0
	}
}

\(2\) 号 DFS：

int pos;//DFS 序的序号
int top[N], tid[N];
void dfs2(int u, int x){
	top[u] = x;//链首
	tid[u] = ++pos;//DFS 序
	if (son[u]) dfs2(son[u], x);//有重儿子，优先遍历重儿子，链首还是为 x
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u]) continue;
		if (v == son[u]) continue;
		dfs2(v, v);//自己单成一条重链，链首为自己
	}
}
  1. 性质
  • 性质 1：树上每个节点都属于且仅属于一条重链。

反证法：

假设 1：点 \(u\) 不属于任意一条重链。

即点 \(u\) 没有重儿子且不是叶子，矛盾。

假设 2：点 \(u\) 属于多条重链。

首先点 \(u\) 一定属于自己的重儿子所在的重链上，分类讨论：

  1. 点 \(u\) 为 \(fa_u\) 的重儿子：

\(fa_u\)，\(u\)，\(son_u\) 处于一条链上，且点 \(u\) 不会再经过其它的链，矛盾。

  1. 点 \(u\) 为 \(fa_u\) 的轻儿子：

\(u\)，\(son_u\) 处于一条链上，且点 \(u\) 不会再经过其它的链，矛盾。

综上，命题得证。

  • 性质 2：\(u\) 与 \(fa_{top_u}\) 一定处于不同的重链上。

令 \(v = top_u\)，仍然采用反证法。

假设 \(v\) 与 \(fa_v\) 处于同一条重链上：

由于 \(v\) 为一条重链的链首，所以 \(v\) 到 \(fa_v\) 的边一定是轻边，故 \(v\) 与 \(fa_v\) 不处于同一条重链上，矛盾。

命题得证。

  1. 应用：

没有什么用的前置铺垫，树链剖分求 LCA：

不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。

向上跳重链时需要先跳所在重链链首深度较大的那个。

int lca(int u, int v){
	while(top[u] != top[v]){
		if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
		else v = fa[top[v]];
	}
	return dep[u] < dep[v] ? u : v;
}

十分简单，下面看例题：

P2590 [ZJOI2008] 树的统计：

根据题目内容，发现你的线段树需要维护三种操作。

  1. 单点修改某个节点的权值。

  2. 查询 \(u\) 到 \(v\) 的路径上的最大权值。

  3. 查询 \(u\) 到 \(v\) 的路径上的权值和。

单点修改很容易实现，问题是如何查询两个节点之间的路径的一些信息。

考虑是如何用倍增求 LCA 的。首先我们将两个节点提到同一高度，然后将两个节点一起向上跳，对于树链剖分也可以使用这样的思想。

在向上跳的过程中，将当前节点向上跳到重链链首，如果该节点已经是链首，向上跳一个节点，直到两个节点相同，顺手查询区间信息。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5, inf = 1e9 + 7;
int n, a[N];
struct asdf{
	int to, next;
}e[N << 1];
int pre[N], k;

void add(int u, int v){
	e[++k] = {v, pre[u]};
	pre[u] = k;
}

struct Segment_Tree{
	struct node{
		int v, add, s;//v 是最大值，s 是和，add 是懒标记
	}t[N << 1];
	//以下是不想解释的线段树
	void pushup(int k){
		t[k].v = max(t[k << 1].v, t[k << 1 | 1].v);
		t[k].s = t[k << 1].s + t[k << 1 | 1].s;
	}
	void pushdown(int k, int l, int r){
		if (t[k].add){
			t[k << 1].v = t[k << 1 | 1].v = t[k << 1].add = t[k << 1 | 1].add = t[k].add;
			int mid = (l + r) >> 1;
			t[k << 1].s = 1ll * (mid - l + 1) * t[k].add;
			t[k << 1 | 1].s = 1ll * (r - mid) * t[k].add;
			t[k].add = 0;
		}
	}
	void build(int k, int l, int r){
		t[k].add = 0;
		if (l == r){
			t[k].v = t[k].s = a[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
		pushup(k);
	}
	void change(int k, int l, int r, int x, int y, int v){
		if (r < x || l > y) return ;
		if (l >= x && r <= y){
			t[k].add = t[k].v = v;
			t[k].s = 1ll * (r - l + 1) * v;
			return ;
		}
		int mid = (l + r) >> 1;
		pushdown(k, l, r);
		change(k << 1, l, mid, x, y, v);
		change(k << 1 | 1, mid + 1, r, x, y, v);
		pushup(k);
	}
	int ask(int k, int l, int r, int x, int y){
		if (l >= x && r <= y) return t[k].v;
		int ans = -inf, mid = (l + r) >> 1;
		pushdown(k, l, r);
		if (x <= mid) ans = max(ans, ask(k << 1, l, mid, x, y));
		if (y >= mid + 1) ans = max(ans, ask(k << 1 | 1, mid + 1, r, x, y));
		return ans;
	}
	int ask2(int k, int l, int r, int x, int y){
		if (l >= x && r <= y) return t[k].s;
		int ans = 0, mid = (l + r) >> 1;
		pushdown(k, l, r);
		if (x <= mid) ans += ask2(k << 1, l, mid, x, y);
		if (y >= mid + 1) ans += ask2(k << 1 | 1, mid + 1, r, x, y);
		return ans;		
	}
	//以上是不想解释的线段树
}chain;

//以下是不想解释的已经讲过的 dfs
int fa[N], sz[N], top[N], tid[N], dep[N], son[N];
int l[N];
void dfs1(int u, int f){
	sz[u] = 1;
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == f) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

int pos;
void dfs2(int u, int x){
	top[u] = x;
	tid[u] = ++pos;
	a[pos] = l[u];
	if (son[u]) dfs2(son[u], x);
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u]) continue;
		if (v == son[u]) continue;
		dfs2(v, v);
	}
}
//以上是不想解释的已经讲过的 dfs

int query(int u, int v){
	int val = -inf, tu = top[u], tv = top[v];//取出 u 和 v 的链首
	while(tu != tv){//一直跳，直到在一条重链上
		if (dep[tu] < dep[tv]){//取深度更深的点进行更新
			swap(u, v);
			swap(tu, tv);
		}
		val = max(val, chain.ask(1, 1, n, tid[tu], tid[u]));//获取 u 到 链首的信息
		u = fa[tu], tu = top[u];//往上跳
	}
	if (tid[u] > tid[v]) swap(u, v);//也是取深度更深的点更新，换了种方式，可以感性理解题解一下
	val = max(val, chain.ask(1, 1, n, tid[u], tid[v]));//更新最大值
	return val;
}

int sum(int u, int v){//同上，改成了求和而已
	int val = 0, tu = top[u], tv = top[v];
	while(tu != tv){
		if (dep[tu] < dep[tv]){
			swap(u, v);
			swap(tu, tv);
		}
		val += chain.ask2(1, 1, n, tid[tu], tid[u]);
		u = fa[tu], tu = top[u];
	}
	if (tid[u] > tid[v]) swap(u, v);
	val += chain.ask2(1, 1, n, tid[u], tid[v]);
	return val;
}

signed main(){
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int u, v;
		scanf("%lld %lld", &u, &v);
		add(u, v), add(v, u);//建边
	}
	for (int i = 1; i <= n; i++) cin >> l[i];//点权
	dfs1(1, 0);//预处理
	dfs2(1, 1);//剖分
	chain.build(1, 1, n);//建维护剖分的线段的线段树
	int q;
	cin >> q;
	while(q--){
		string s;
		int x, y;
		cin >> s >> x >> y;
		if (s[0] == 'Q'){
			if (s[1] == 'M') cout << query(x, y) << "\n";//和
			else cout << sum(x, y) << "\n";//最大值
		}
		else{
			chain.change(1, 1, n, tid[x], tid[x], y);//单点修改
		}
	}
	return 0;
}

P4114 Qtree1：

和上题没有多大的不一样的地方，只是把维护点权变成了维护边权，将 \(u-v\) 边权转化为点 \(u\) 的点权即可，根节点没有权值。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;
int n, a[N];
struct asdf{
	int to, next, len;
}e[N << 1];
int pre[N], k;

void add(int u, int v, int w){
	e[++k] = {v, pre[u], w};
	pre[u] = k;
}

struct Segment_Tree{
	struct node{
		int v, add;//v 表示最大值
	}t[N << 1];
	//以下是仍然不想解释的线段树
	void pushup(int k){
		t[k].v = max(t[k << 1].v, t[k << 1 | 1].v);
	}
	void pushdown(int k){
		if (t[k].add){
			t[k << 1].v = t[k << 1 | 1].v = t[k << 1].add = t[k << 1 | 1].add = t[k].add;
			t[k].add = 0;
		}
	}
	void build(int k, int l, int r){
		t[k].add = 0;
		if (l == r){
			t[k].v = a[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
		pushup(k);
	}
	void change(int k, int l, int r, int x, int y, int v){
		if (r < x || l > y) return ;
		if (l >= x && r <= y){
			t[k].add = t[k].v = v;
			return ;
		}
		int mid = l + r >> 1;
		pushdown(k);
		change(k << 1, l, mid, x, y, v);
		change(k << 1 | 1, mid + 1, r, x, y, v);
		pushup(k);
	}
	int ask(int k, int l, int r, int x, int y){
		if (l >= x && r <= y) return t[k].v;
		int ans = 0, mid = (l + r) >> 1;
		pushdown(k);
		if (x <= mid) ans = max(ans, ask(k << 1, l, mid, x, y));
		if (y >= mid + 1) ans = max(ans, ask(k << 1 | 1, mid + 1, r, x, y));
		return ans;
	}
	//以上是仍然不想解释的线段树
}chain;

//以下是仍然不想解释的 DFS
int fa[N], sz[N], top[N], tid[N], dep[N], son[N], l[N];
void dfs1(int u, int f){
	sz[u] = 1;
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == f) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		l[v] = e[i].len;//这里说一下，边权转点权
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

int pos;
void dfs2(int u, int x){
	top[u] = x;
	tid[u] = ++pos;
	a[pos] = l[u];//这里再说一下，边权转点权
	if (son[u]) dfs2(son[u], x);
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u]) continue;
		if (v == son[u]) continue;
		dfs2(v, v);
	}
}
//以上是仍然不想解释的 DFS
//以下是不想解释的区间查询
int query(int u, int v){
	int val = 0, tu = top[u], tv = top[v];
	while(tu != tv){
		if (dep[tu] < dep[tv]){
			swap(u, v);
			swap(tu, tv);
		}
		val = max(val, chain.ask(1, 1, n, tid[tu], tid[u]));
		u = fa[tu], tu = top[u];
	}
	if (tid[u] > tid[v]) swap(u, v);
	val = max(val, chain.ask(1, 1, n, tid[u] + 1, tid[v]));
	return val;
}
//以上是不想解释的区间查询

signed main(){
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int u, v, w;
		scanf("%lld %lld %lld", &u, &v, &w);
		add(u, v, w), add(v, u, w);//建边
	}
	dfs1(1, 0);
	dfs2(1, 1);
	chain.build(1, 1, n);
	while(1){
		string s;
		cin >> s;
		if (s == "DONE") break;
		if (s == "QUERY"){
			int u, v;
			cin >> u >> v;
			if (u == v) puts("0");//如题意
			else cout << query(u, v) << "\n";//查询
		}
		else{
			int u, t;
			cin >> u >> t;
			if (dep[e[u * 2].to] > dep[e[u * 2 - 1].to]) u = e[u * 2].to;//得到边 u 所对应的点
			else u = e[u * 2 - 1].to;//同上
			chain.change(1, 1, n, tid[u], tid[u], t);//单点修改（即使我写的是区间修改）
		}
	}
	return 0;
}

P3038 [USACO11DEC] Grass Planting G：

同 P4114，需要将边权转化为点权，然后变成了区间修改，单点查询，因为我懒得改代码所以写的是区间查询（）。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;
int n, m, a[N];
struct asdf{
	int to, next, len;
}e[N << 1];
int pre[N], k;

void add(int u, int v, int w){
	e[++k] = {v, pre[u], w};
	pre[u] = k;
}

//以下是不想解释的线段树
struct Segment_Tree{
	struct node{
		int v, add;
	}t[N << 1];
	void pushup(int k){
		t[k].v = max(t[k << 1].v, t[k << 1 | 1].v);
	}
	void pushdown(int k){
		if (t[k].add){
			t[k << 1].v += t[k].add;
			t[k << 1 | 1].v += t[k].add;
			t[k << 1].add += t[k].add;
			t[k << 1 | 1].add += t[k].add;
			t[k].add = 0;
		}
	}
	void build(int k, int l, int r){
		t[k].add = 0;
		if (l == r){
			t[k].v = a[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
		pushup(k);
	}
	void change(int k, int l, int r, int x, int y, int v){
		if (r < x || l > y) return ;
		if (l >= x && r <= y){
			t[k].add += v;
			t[k].v += v;
			return ;
		}
		int mid = l + r >> 1;
		pushdown(k);
		change(k << 1, l, mid, x, y, v);
		change(k << 1 | 1, mid + 1, r, x, y, v);
		pushup(k);
	}
	int ask(int k, int l, int r, int x, int y){
		if (r < x || l > y) return 0;
		if (l >= x && r <= y) return t[k].v;
		int mid = (l + r) >> 1;
		pushdown(k);
		return max(ask(k << 1, l, mid, x, y), ask(k << 1 | 1, mid + 1, r, x, y));
	}
}chain;
//以上是不想解释的线段树

//以下是不想解释的 DFS
int fa[N], sz[N], top[N], tid[N], dep[N], son[N], l[N];
void dfs1(int u, int f){
	sz[u] = 1;
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == f) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		l[v] = e[i].len;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

int pos;
void dfs2(int u, int x){
	top[u] = x;
	tid[u] = ++pos;
	a[pos] = l[u];
	if (son[u]) dfs2(son[u], x);
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u]) continue;
		if (v == son[u]) continue;
		dfs2(v, v);
	}
}
//以上是不想解释的 DFS

//以下是不想解释的区查
int query(int u, int v){
	int val = 0, tu = top[u], tv = top[v];
	while(tu != tv){
		if (dep[tu] < dep[tv]){
			swap(u, v);
			swap(tu, tv);
		}
		val = max(val, chain.ask(1, 1, n, tid[tu], tid[u]));
		u = fa[tu], tu = top[u];
	}
	if (tid[u] > tid[v]) swap(u, v);
	val = max(val, chain.ask(1, 1, n, tid[u] + 1, tid[v]));
	return val;
}
//以上是不想解释的区查

void update(int u, int v){
	int tu = top[u], tv = top[v];//得到链首
	while(tu != tv){
		if (dep[tu] < dep[tv]){//选更深的跳
			swap(u, v);
			swap(tu, tv);
		}
		chain.change(1, 1, n, tid[tu], tid[u], 1);//修改
		u = fa[tu], tu = top[u];//跳就完事了
	}
	if (tid[u] > tid[v]) swap(u, v);//选更深的
	chain.change(1, 1, n, tid[u] + 1, tid[v], 1);//避开点 u，因为将边权转为了点权
}

//以下是不想解释的主函数
signed main(){
	cin >> n >> m;
	for (int i = 1; i <= n - 1; i++){
		int u, v;
		scanf("%lld %lld", &u, &v);
		add(u, v, 1), add(v, u, 1);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	chain.build(1, 1, n);
	while(m--){
		string s;
		cin >> s;
		if (s == "Q"){
			int u, v;
			cin >> u >> v;
			if (fa[u] == v) cout << chain.ask(1, 1, n, tid[u], tid[u]) - 1 << "\n";
			else if (fa[v] == u) cout << chain.ask(1, 1, n, tid[v], tid[v]) - 1 << "\n";
		}
		else{
			int u, v;
			cin >> u >> v;
			update(u, v);
		}
	}
	return 0;
}
//以上是不想解释的主函数

P3384 【模板】重链剖分/树链剖分：

啥，你问我为什么做了三道题才到模板题？

沉思.jpg。

哦，因为这题里又多了两个操作，且修改和查询操作都是区间的，所以放后面点。

多了取模和子树操作，取模好解决，子树操作怎么办？

因为每个子树的 \(tid\) 都是连续的，于是直接线段树暴力区间修改/查询即可。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 5, inf = 1e9 + 7;
int n, m, r, p, a[N];
struct asdf{
	int to, next;
}e[N << 1];
int pre[N], k;

void add(int u, int v){
	e[++k] = {v, pre[u]};
	pre[u] = k;
}

struct Segment_Tree{
	struct node{
		int add, s;
	}t[N << 1];
	void pushup(int k){
		t[k].s = t[k << 1].s + t[k << 1 | 1].s;
		t[k].s %= p;
	}
	void pushdown(int k, int l, int r){
		if (t[k].add){
			t[k << 1].add = (t[k << 1].add + t[k].add) % p;
			t[k << 1 | 1].add = (t[k << 1 | 1].add + t[k].add) % p;
			int mid = (l + r) >> 1;
			t[k << 1].s = (t[k << 1].s + 1ll * (mid - l + 1) * t[k].add % p) % p;
			t[k << 1 | 1].s = (t[k << 1 | 1].s + 1ll * (r - mid) * t[k].add % p) % p;
			t[k].add = 0;
		}
	}
	void build(int k, int l, int r){
		t[k].add = 0;
		if (l == r){
			t[k].s = a[l];
			return ;
		}
		int mid = (l + r) >> 1;
		build(k << 1, l, mid);
		build(k << 1 | 1, mid + 1, r);
		pushup(k);
	}
	void change(int k, int l, int r, int x, int y, int v){
		if (r < x || l > y) return ;
		if (l >= x && r <= y){
			t[k].add = (t[k].add + v) % p;
			t[k].s = (t[k].s + 1ll * (r - l + 1) * v % p) % p;
			return ;
		}
		int mid = (l + r) >> 1;
		pushdown(k, l, r);
		change(k << 1, l, mid, x, y, v);
		change(k << 1 | 1, mid + 1, r, x, y, v);
		pushup(k);
	}
	int ask(int k, int l, int r, int x, int y){
		if (l >= x && r <= y) return t[k].s % p;
		int ans = 0, mid = (l + r) >> 1;
		pushdown(k, l, r);
		if (x <= mid) ans = (ans + ask(k << 1, l, mid, x, y)) % p;
		if (y >= mid + 1) ans = (ans + ask(k << 1 | 1, mid + 1, r, x, y)) % p;
		return ans % p;
	}
}chain;

int fa[N], sz[N], top[N], tid[N], dep[N], son[N];
int l[N];
void dfs1(int u, int f){
	sz[u] = 1;
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == f) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}

int pos;
void dfs2(int u, int x){
	top[u] = x;
	tid[u] = ++pos;
	a[pos] = l[u];
	if (son[u]) dfs2(son[u], x);
	for (int i = pre[u]; i; i = e[i].next){
		int v = e[i].to;
		if (v == fa[u]) continue;
		if (v == son[u]) continue;
		dfs2(v, v);
	}
}

void update(int u, int v, int w){
	w %= p;
	int tu = top[u], tv = top[v];
	while(tu != tv){
		if (dep[tu] < dep[tv]){
			swap(u, v);
			swap(tu, tv);
		}
		chain.change(1, 1, n, tid[tu], tid[u], w);
		u = fa[tu], tu = top[u];
	}
	if (tid[u] > tid[v]) swap(u, v);
	chain.change(1, 1, n, tid[u], tid[v], w);
}

int query(int u, int v){
	int val = 0, tu = top[u], tv = top[v];
	while(tu != tv){
		if (dep[tu] < dep[tv]){
			swap(u, v);
			swap(tu, tv);
		}
		val += chain.ask(1, 1, n, tid[tu], tid[u]);
		u = fa[tu], tu = top[u];
	}
	if (tid[u] > tid[v]) swap(u, v);
	val += chain.ask(1, 1, n, tid[u], tid[v]);
	return val;
}
//以上全都不想解释了

signed main(){
	cin >> n >> m >> r >> p;
	for (int i = 1; i <= n; i++) cin >> l[i];
	for (int i = 1; i <= n - 1; i++){
		int u, v;
		scanf("%lld %lld", &u, &v);
		add(u, v), add(v, u);
	}
	dfs1(r, 0);
	dfs2(r, r);
	chain.build(1, 1, n);
	while(m--){
		int opt, x, y, z;
		cin >> opt >> x;
		if (opt == 1){
			cin >> y >> z;
			update(x, y, z);
		}
		else if (opt == 2){
			cin >> y;
			cout << query(x, y) % p << "\n";
		}
		else if (opt == 3){
			cin >> y;
			y %= p;
			chain.change(1, 1, n, tid[x], tid[x] + sz[x] - 1, y);//子树操作，暴力修改
		}
		else{
			cout << chain.ask(1, 1, n, tid[x], tid[x] + sz[x] - 1) % p << "\n";//子树操作，暴力查询
		}
	}
	return 0;
}

想听的更详细点可以翻翻上面题目的题解。

思考题：P2486 [SDOI2011] 染色。

这里大致讲下思路，全部代码请读者自行实现。

就是多维护每个线段树节点的左端点颜色和右端点颜色，然后查询的时候时刻检查 lson 的右端点颜色和 rson 的左端点颜色是否一样，一样则将连续段数减一，重链剖分的查询同理。

三，尾声

终于没了，Markdown编辑界面已经较卡了，所以长链剖分咕到另一篇笔记里去吧。

标签：剖分,int,top,tu,笔记,树链,tv,tid,son
From： https://www.cnblogs.com/lyingf-hq/p/18135708

相关文章

  • day06_我的Java学习笔记 (综合应用专题课)
    专题课（综合案例）案例一：买飞机票案例二：找素数上述老师代码有点问题，即：j<i/2;应为j<=i/2;见如下判断：其实出问题的点，只会在i=4时，因为当i=4时，j<i/2：不成立，直接跳过该循环，执行步骤3的操作了。（当范围不是101-200，而是包含了4，则会出现上述的现象，因4不满......
  • day04_我的Java学习笔记 (数组的静态初始化、数组的动态初始化，debug调试等)
    1.数组1.1数组的定义那python怎么定义数组的呢?Java:String[]names={"zhangsan","lisi","wangwu"}Python:names=["zhangsan","lisi","wangwu"]在python中，列表可以存储不同类型的数据，而在Java中，数组只能存储相同类型的数据。1......
  • day02_我的Java学习笔记 (类型转换、+做连接符、变量自增自减运算、三元运算符、键盘
    Java语言基础知识1.类型转换1.1自动类型转换1.2表达式的自动类型转换1.3强制类型转换这里得出的结果为啥是-36呢？？？后面高级篇再细讲。2.运算符2.1算数运算符2.1.1基本算数运算符2.1.2案例：数值拆分2.2+符号做连接符【思考1】：a+'a'为啥......
  • day01-02_我的Java学习笔记 (IDEA的安装、配置及使用、IDEA常用快捷键、IEDA创建空工
    1.IDEA的安装及配置1.1IDEA的安装具体操作，详见《04、IDEA安装详解.pdf》1.2IDEA主题配置、字体配置1.3IDEA常用快捷键1.4IDEA修改快捷键在IDEA工具中，Ctrl+空格的快捷键，可以帮助我们补全代码，但是这个快捷键和Windows中的输入法切换快捷键冲突，需要修改IDEA中......
  • day01-03_我的Java学习笔记(Java基础语法--注释、字面量、变量、二进制、ASCII编码、
    1.Java基础语法1.1注释1.2字面量(Python中叫数据类型)1.3变量1.3.1变量的定义及使用1.3.2变量使用注意事项1.4数据的存储形式：二进制字节、字、bit、byte的关系：字word字节byte位bit，来自英文bit，音译为“比特”，表示二进制位。字长是指字的......
  • 《线性代数的本质》笔记（04-附注1-05）
    04-矩阵乘法与线性变换复合的联系问：如何描述连续两个线性变换？答：先左乘一个矩阵，再左乘一个。如果我们用一个矩阵来描述这个复合过程，那么这个矩阵应该等于两个矩阵的乘积，这就是矩阵的乘法。如何理解上图：把右侧矩阵M2看作看作第一次变换后的\(\hat{i}\)向量和\(\hat{j}\)向量，......
  • 抽象代数课程笔记
    抽象代数的意义：\(\newcommand{\a}{\alpha}\newcommand{\b}{\beta}\newcommand{\D}{\Delta}\newcommand{\eps}{\varepsilon}\newcommand{\ph}{\varphi}\newcommand{\t}{\theta}\newcommand{\la}{\lambda}\newcommand{\si}{\sigma}\newcommand{\d......
  • 《人人都是产品经理》笔记分享
    通过最近对《人人都是产品经理》书籍的学习，理解，讨论，再总结。个人觉得收获很大，总结出课程大纲并夹带者一些理解以读书笔记的形式分享给大家。有理解不到位的地方，请各位读者海涵。最后感谢苏杰老师的知识分享，使得每个读者心中有一颗产品意识的种子，在未来的某一天悄然发芽。0.0......
  • 《梁宁产品思维30讲》笔记分享
    通过最近对《梁宁产品思维30讲》课程的学习，理解，讨论，再总结。个人觉得收获很大，总结出课程大纲并夹带者一些理解以读书笔记的形式分享给大家。有理解不到位的地方，请各位读者海涵。最后感谢梁宁老师的知识分享，使得每个读者心中有一个产品意识的种子，在未来的某一天悄然发芽。发刊......
  • numpy库零散笔记
    创建数组1.用ndarraynumpy.array(object,dtype=None,copy=True,order=None,subok=False,ndmin=0)参数描述object数组或嵌套的数列dtype数组元素的数据类型，可选copy对象是否需要复制，可选order创建数组的样式，C为行方向，F为列方向，A为任意方......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99