• （动态）树分治 学习笔记

    浅谈一下学了好久的树分治。

    一、点分治

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

    P3806 【模板】点分治1

    很基础的了，询问树上距离为 k k k 的点对是否存在。

    大概就是每次找重心当作根，对于当前的根，统计每个子节点到它的距离，然后用双指针遍历，当且仅当两个儿子到当前根的距离之和为 k k k 且来自根的不同子树时，这两个子节点的距离就为 k k k，那么距离为 k k k 的点对存在。

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

#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 1e4 + 5;
const int maxm = 105;
int n, m, q[maxm];
bool k[maxm], vis[maxn];
int cnt, hd[maxn];
struct node{
	int to, nxt, w;
}e[maxn << 1];
int a[maxn], tot, d[maxn], b[maxn], mxs[maxn], siz[maxn];
int rt;

inline void add(int u, int v, int w)
{
	e[++cnt].to = v;
	e[cnt].nxt = hd[u], hd[u] = cnt;
	e[cnt].w = w;
}

inline void getrt(int u, int fa, int sum)
{
	siz[u] = 1, mxs[u] = 0;
	for(int i = hd[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(vis[v] or v == fa) continue;
		getrt(v, u, sum);
		mxs[u] = max(mxs[u], siz[v]);
		siz[u] += siz[v];
	}
	mxs[u] = max(mxs[u], sum - siz[u]);
	if(!rt or mxs[rt] > mxs[u]) rt = u;
}

inline void getdis(int u, int fa, int dis, int anc)
{
	a[++tot] = u, d[u] = dis, b[u] = anc;
	for(int i = hd[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa or vis[v]) continue;
		getdis(v, u, dis + e[i].w, anc);
	}
}

inline bool cmp(int x, int y)
{
	return d[x] < d[y];
}

inline void clc(int u)
{
	tot = 0;
	/*
	记当前分治的根为 rootroot。
	a 数组记录从 root 能到的点;
	d 数组记录 ai 到 root 的距离;
	b 数组记录 ai属于 root 的哪一棵子树(即当 b[a[i]]=b[a[j] 时,说明 a[i]与 a[j]属于 rootroot 的同一棵子树)
	*/
	a[++tot] = u, b[u] = u, d[u] = 0;
	for(int i = hd[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(vis[v]) continue;
		getdis(v, u, e[i].w, v);
	}
	sort(a + 1, a + tot + 1, cmp);
	rep(i, 1, m)
	{
		if(k[i]) continue;
		int l = 1, r = tot;
		while(l < r)
		{
			int w = d[a[l]] + d[a[r]];
			if(w < q[i]) l += 1;
			else if(w > q[i]) r -= 1;
			else if(b[a[l]] == b[a[r]])
				if(d[a[r]] == d[a[r - 1]]) r -= 1;
				else l += 1;
			else
			{
				k[i] = 1;
				break;
			}
		}
	}
}

inline void slv(int u)
{
	vis[u] = 1;
	clc(u);
	for(int i = hd[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(vis[v]) continue;
		rt = 0, getrt(v, 0, siz[v]);
		slv(rt);	
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	rep(i, 1, n - 1)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		add(u, v, w), add(v, u, w);
	}
	rep(i, 1, m) 
	{
		scanf("%d", &q[i]);
		if(!q[i]) k[i] = 1;
	}
	mxs[0] = n;
	getrt(1, 0, n);
	slv(rt);
	rep(i, 1, m) 
		if(k[i]) printf("AYE\n");
		else printf("NAY\n");
	return 0;
}

    • 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
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126

    另一道类似的升级题：P4178 Tree。

    题意变为求出树上两点距离小于等于 k k k 的点对数量。思路差不多，不过是在遍历统计答案的时候使用双指针统计答案，即合法点对个数。但是要注意，如果只是单单这样，显然双指针会把这种情况统计进去：

    （图自此博客。）

    所以再套个容斥就好了。

    code

    二、动态点分治/点分树

    感觉这个东西还是比较灵活的。

    P6329 【模板】点分树 | 震波

    所有与 x x x 距离不超过 k k k 的城市都将受到影响，求该次地震造成的经济损失，即所有受影响城市的价值和，待修改（修改某节点价值）。强制在线。

    首先提出一个关于点分树的概念——重构树。即把当前树的重心和上一层的树重心连边，后者是前者父亲。这样得到的重构树形态优秀，有利于解决和树的形态无关的问题。

    剩下具体怎么在重构树上查询距离、记录距离等等见此题解。

    其中还用了一个 O ( 1 ) \mathcal{\text{O}}(1) O(1) 求 LCA 的小技巧。

    特别要注意的一点是：我们再构造重构树之前就已经记录下原树上两个节点的距离了，后续题目不会再对树的形态进行改变了，所以方法可行。

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

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define go(u) for(int i = hd[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
const int maxn = 2e5 + 5;
const int inf = 1e9 +7;
int n, m;
int a[maxn], cnt, hd[maxn];
struct node{
	int to, nxt;
}e[maxn << 1];
int pos[maxn], id[maxn], tot;
int st[maxn << 1][21], dep[maxn], rt, sum;
int siz[maxn], fa[maxn], lg[maxn << 1];
bool vis[maxn];
int ans, mxx;
vector <int> c[2][maxn];

inline void add(int u, int v){
	e[++cnt] = (node){v, hd[u]};
	hd[u] = cnt;
}

inline void dfs1(int u, int f){
	st[++tot][0] = u, pos[u] = tot;
	go(u) if(v != f){
		dep[v] = dep[u] + 1, dfs1(v, u);
		st[++tot][0] = u;
	}
}

inline int minn(int a, int b){
	return dep[a] < dep[b] ? a : b;
}

inline void pre(){
	lg[0] = -1;
	rep(i, 1, tot) lg[i] = lg[i / 2] + 1;
	for(int k = 1; (1 << k) <= cnt; ++k)
		for(int i = 1; i + (1 << k) <= cnt; ++i)
			st[i][k] = minn(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}

inline void findrt(int u, int f){
	siz[u] = 1;
	int mxs = 0;
	go(u) if(v != f and !vis[v]){
		findrt(v, u), siz[u] += siz[v];
		mxs = max(mxs, siz[v]);
	}
	mxs = max(mxs, sum - mxs);
	if(!rt or mxs < mxx) rt = u, mxx = mxs;
}

inline void build(int u){
	vis[u] = 1, siz[u] = sum + 1;
	c[0][u].resize(siz[u] + 1), c[1][u].resize(siz[u] + 1);
	go(u) if(!vis[v]){
		sum = siz[v], rt = 0, mxx = -inf, findrt(v, u);
		fa[rt] = u, build(rt);
	}
}

inline int gdis(int u, int v){
	if(pos[u] > pos[v]) swap(u, v);
	int x = pos[u], y = pos[v], k = y - x + 1;
	int lca = minn(st[x][lg[k]], st[y - (1 << lg[k]) + 1][lg[k]]);
	return dep[u] + dep[v] - 2 * dep[lca];
}

inline int lb(int x){
	return x & (-x);	
}

inline void update(int u, int opt, int x, int w){
	x += 1;
	for(int i = x; i <= siz[u]; i += lb(i)) 
		c[opt][u][i] += w;
}

inline int query(int x, int opt, int y){
	y += 1;
	int res = 0;
	for(int i = min(y, siz[x]); i; i -= lb(i))
		res += c[opt][x][i];
	return res;
}

inline void update_path(int x, int w){
	for(int i = x; i; i = fa[i]) update(i, 0, gdis(x, i), w);
	for(int i = x; fa[i]; i = fa[i]) update(i, 1, gdis(x, fa[i]), w);
}

int main(){
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]);
	rep(i, 2, n){
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	dep[1] = 1, dfs1(1, 0), pre();
	sum = n, mxx = -inf, findrt(1, 0), build(rt);
	rep(i, 1, n) update_path(i, a[i]);
	rep(i, 1, m){
		int opt, x, y;
		scanf("%d%d%d", &opt, &x, &y);
		x ^= ans, y ^= ans;
		if(!opt){
			ans = query(x, 0, y);
			for(int i = x; fa[i]; i = fa[i]){
				int dis = gdis(fa[i], x);
				if(y >= dis)
					ans += query(fa[i], 0, y - dis) - query(i, 1, y - dis);
			}
			printf("%d\n", ans);
		}
		else update_path(x, y - a[x]), a[x] = y;
	}
	return 0;
}	

    • 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
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122

    重构树的具体应用可以见下述的“动态树分治”。

    三、动态树分治

    模板：P4719 【模板】“动态 DP”&动态树分治

    动态树分治，也叫动态 DP 问题，是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题。

    tips: \mathcal{\text{tips:}} tips: 本题中独立集指无向图中互不相邻的点组成的集合，最大权独立集指无向图中权值和最大的独立集。

    首先我们把不带修改的 dp 问题进行求解，求出它的转移方程。

    然后带上修改。不难发现，如果更改了某一节点的权值，那么它到该树根节点路径上所有的节点的 dp 值都会受到影响。所以为了保证 O ( l o g n ) \mathcal{\text{O}}(logn) O(logn) 的复杂度，我们使用重链剖分。

    然后再去优化转移方程（即是把方程里面的 ∑ \sum ∑ 去掉），这样以来，我们发现对于区间（即一条重链）内的区间加并不好处理，所以用矩阵乘法把它优化成区间“乘积”。

    但是这样有又了新问题：优化后的转移方程和平时常用的矩阵乘法运算不一样（转移方程内有一个取 m a x max max 的步骤，但矩阵乘法中没有）。所以我们重新定义矩阵乘法。

    然后再根据转移方程去构造转移矩阵。

    这样，我们就把修改操作转换为区间乘了，对于每条重链我们用线段树维护即可。

    其余转移方程、矩阵乘法重定义、转移矩阵等具体内容见此博客（题解）。

    代码：

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

#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define go(u) for(int i = hd[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
const int maxn = 1e5 + 5;
const int maxm = 4e5 + 5;
int n, m;
int a[maxn], cnt, hd[maxn];
int tot, id[maxn], dfn[maxn], siz[maxn];
int mxs[maxn], f[maxn][2], fa[maxn];
int top[maxn], ed[maxn];
struct node{
	int to, nxt;
}e[maxn << 1];
struct matrix{
	int mt[2][2];
	matrix(){
		memset(mt, -0x3F, sizeof mt);	
	}
	inline matrix operator * (matrix b){
		matrix c;
		rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1)
			c.mt[i][j] = max(c.mt[i][j], mt[i][k] + b.mt[k][j]);
		return c;
	}
}val[maxn], tr[maxm];
int L[maxm], R[maxm];

inline void add(int u, int v){
	e[++cnt] = (node){v, hd[u]};
	hd[u] = cnt;
}

inline void dfs1(int u){
	siz[u] = 1;
	go(u) if(v != fa[u]){
		fa[v] = u, dfs1(v);
		siz[u] += siz[v];
		if(siz[v] > siz[mxs[u]]) mxs[u] = v;
	}
}

inline void dfs2(int u, int anc){
	id[u] = ++tot, dfn[tot] = u;
	top[u] = anc, ed[anc] = max(ed[anc], id[u]);
	f[u][0] = 0, f[u][1] = a[u];
	val[u].mt[0][0] = val[u].mt[0][1] = 0;
	val[u].mt[1][0] = a[u];
	if(mxs[u]){
		dfs2(mxs[u], anc);
		f[u][0] += max(f[mxs[u]][0], f[mxs[u]][1]), 
		f[u][1] += f[mxs[u]][0];
	}
	go(u) if(v != mxs[u] and v != fa[u]){
		dfs2(v, v);
		f[u][0] += max(f[v][0], f[v][1]);
		f[u][1] += f[v][0];
		val[u].mt[0][0] += max(f[v][0], f[v][1]);
		val[u].mt[0][1] = val[u].mt[0][0];
		val[u].mt[1][0] += f[v][0];
	}
}

inline void up(int x){
	tr[x] = tr[x << 1] * tr[x << 1 | 1];
}

inline void build(int i, int l, int r){
	L[i] = l, R[i] = r;
	if(l == r){
		tr[i] = val[dfn[l]];
		return;
	}
	int mid = l + r >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	up(i);
}

inline void update(int i, int pos){
	if(L[i] == R[i]){
		tr[i] = val[dfn[pos]];
		return;
	}
	int mid = L[i] + R[i] >> 1;
	if(pos <= mid) update(i << 1, pos);
	else update(i << 1 | 1, pos);
	up(i);
}

inline matrix query(int i, int l, int r){
	if(L[i] >= l and R[i] <= r) return tr[i];
	int mid = L[i] + R[i] >> 1;
	if(r <= mid) return query(i << 1, l, r);
	else if(l > mid) return query(i << 1 | 1, l, r);
	else return query(i << 1, l, r) * query(i << 1 | 1, l, r);
}

inline void update_path(int u, int k){
	val[u].mt[1][0] += k - a[u], a[u] = k;
	matrix bef, aft;
	while(u > 0){
		bef = query(1, id[top[u]], ed[top[u]]);
		update(1, id[u]);
		aft = query(1, id[top[u]], ed[top[u]]);
		u = fa[top[u]];
		val[u].mt[0][0] += max(aft.mt[0][0], aft.mt[1][0]) - max(bef.mt[0][0], bef.mt[1][0]);
		val[u].mt[0][1] = val[u].mt[0][0];
		val[u].mt[1][0] += aft.mt[0][0] - bef.mt[0][0];
	}
}

int main(){
	scanf("%d%d", &n, &m);
	rep(i, 1, n) scanf("%d", &a[i]);
	rep(i, 2, n){
		int u, v;
		scanf("%d%d", &u, &v), add(u, v), add(v, u);
	}
	dfs1(1), dfs2(1, 1);
	build(1, 1, n);//线段树叶子节点 i 代表 dfs序第 i 个的 val 值
	rep(i, 1, m){
		int u, k;
		scanf("%d%d", &u, &k);
		update_path(u, k);
		matrix fin = query(1, 1, ed[1]);//need to test
		printf("%d\n", max(fin.mt[0][0], fin.mt[1][0]));
	}
	return 0;
}

    • 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
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130

    例题：P3920 [WC2014]紫荆花之恋

    大视野上把它归在动态树分治里，但是 solution \text{solution} solution 里可谓是八仙过海。

    我贺的是林教练的做法：分情况讨论 + 替罪羊树思想 + 平衡树。所以也不算是动态树分治了。
    具体地：【LG-P3920/WC2014】 紫荆花之恋-题解（by 531）。

    例题：P2056 [ZJOI2007] 捉迷藏

    （其实也算是动态点分治的例题…

    不带修改，就是经典的树上两点距离最大值的求解。

    所以我们要动态维护每个节点子树内最大值和次大值，此处对于每个节点采用两个堆维护。

    在重构树的基础上进行查询修改操作即可。code.

    —— E n d End End——

  • 相关阅读:
    简简单单一段话描述设计模式
    Django笔记十八之save函数的继承操作和指定字段更新等实例方法
    Sui上低Gas费为预言机注入强大动力
    自然语言处理（NLP）—— 神经网络自然语言处理（2）实际应用
    Qt+ECharts开发笔记（一）：ECharts介绍、下载和Qt调用ECharts基础柱状图Demo
    SpringBoot开发使用篇(1)—
    安全扫描项目
    MYSQL--未提交(read uncommitted)、读已提交(read committed)和repeatable read(可重复读)
    es6---模块化
    [附源码]java毕业设计教务系统
  • 原文地址：https://blog.csdn.net/ez_gsn/article/details/125541738