树链剖分题型总结一

树链剖分模板题

首先是树链剖分模板题
一般的我将树按轻重儿子建立DFS序列
dfs1 处理轻重儿子子树大小之后的dfs2 就方便处理轻重链的分离了
从而线段数维护 dfs序列将一个树上问题转到区间一维的
性质1
如果边 $(u, v)$ ,为轻边,那么 $S i z e (v) \leq S i z e (u) / 2$

证明：显然，否则该边会成为重边

性质2
树中任意两个节点之间的路径中轻边的条数不会超过 $\log_{2} n$ ,重路径的数目不会超过 $\log_{2} n$

这样的话重路最多lg 个，线树维护复杂度也是lg的这样总复杂度是 $l g^{2} n$ 的
洛谷树链剖分模板题 https://www.luogu.org/problem/P3384
这篇博客放2个点剖的题之后边剖下一篇博客发

#include <bits/stdc++.h>
#define debug(x, str) cout << (str) << " = [ << : " << (x) << " ]" << endl;
//#define fastio ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, k, m, mod;
int head[maxn], val[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1];

void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

int fa[maxn], dep[maxn], siz[maxn], son[maxn];
void dfs1(int u, int f) {
	fa[u] = f;
	dep[u] = dep[f] + 1;
	siz[u] = 1;
	int maxsize = -1;
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == f) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > maxsize) {
			maxsize = siz[v];
			son[u] = v;
		}
	}
}

int tim, dfn[maxn], top[maxn], w[maxn];
void dfs2(int u, int t) {
	dfn[u] = ++ tim;
	top[u] = t;
	w[tim] = val[u];
	if(!son[u]) return;
	dfs2(son[u], t);
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}

int tree[maxn << 2], lazy[maxn << 2];
void push_up(int rt) {
	tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod;
}

void push_down(int rt, int l, int r, int mid) {
	if(!lazy[rt]) return;
	lazy[rt << 1] = (lazy[rt] + lazy[rt << 1]) % mod;
	lazy[rt << 1 | 1] = (lazy[rt] + lazy[rt << 1 | 1]) % mod;
	tree[rt << 1] = (tree[rt << 1]  + (mid - l + 1) * lazy[rt] % mod) % mod;
	tree[rt << 1 | 1] = (tree[rt << 1 | 1]  + (r - mid) * lazy[rt] % mod) % mod;
	lazy[rt] = 0;
}

void build(int l, int r, int rt) {
	lazy[rt] = 0;
	if(l == r) {
		tree[rt] = w[l] % mod;
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	push_up(rt);
}

void updata(int L, int R, int l, int r, int rt, int val) {
	if(L <= l && r <= R) {
		tree[rt] = (tree[rt] + val * (r - l + 1) % mod) % mod;
		lazy[rt] = (lazy[rt] + val) % mod;
		return ;
	}
	int mid = l + r >> 1;
	push_down(rt, l, r, mid);
	if(L <= mid) updata(L, R, l, mid, rt << 1, val);
	if(R > mid) updata(L, R, mid + 1, r, rt << 1 | 1, val);
	push_up(rt);
}

int query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return tree[rt];
	}
	int mid = l + r >> 1;
	push_down(rt, l, r, mid);
	int res = 0;
	if(L <= mid) res = (res + query(L, R, l, mid, rt << 1)) % mod;
	if(R > mid) res = (res +query(L, R, mid + 1, r, rt << 1 | 1)) % mod;
	return res;
}

void mson(int x, int z) {
	updata(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1, z);
}

int qson(int x) {
	return query(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1);
}

void mchain(int x, int y, int z) {
	z %= mod;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		updata(dfn[top[x]], dfn[x], 1, n, 1, z);
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	updata(dfn[x], dfn[y], 1, n, 1, z);
}

int qchain(int x, int y) {
	int ret = 0;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = (ret + query(dfn[top[x]], dfn[x], 1, n, 1)) % mod;
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = (ret + query(dfn[x], dfn[y], 1, n, 1)) % mod;
	return ret;
}

signed main() {
// freopen("in.in","r",stdin);
	int op, x, y, k, r;
	scanf("%d %d %d %d", &n, &m ,& r, &mod);
	for(int i = 1; i <= n; i ++) cin >> val[i];
	for(int i = 1, a, b; i < n; i ++) {
		scanf("%d %d", &a, &b);
		ade(a, b), ade(b, a);
	}
	dfs1(r, -1);
	dfs2(r, -1);
	build(1, n, 1);
	while(m --) {
		scanf("%d %d", &op, &x);
		if(op == 1) {
			scanf("%d %d", &y, &k);
			mchain(x, y, k);
		} else if(op == 2) {
			scanf("%d", &y);
			printf("%d\n", qchain(x, y));
		} else if(op == 3) {
			scanf("%d", &k);
			mson(x, k);
		} else if(op == 4) {
			printf("%d\n", qson(x));
		}
	}
	return 0;
}

P2146 [NOI2015]软件包管理器

https://www.luogu.org/problem/P2146
这道题正常的建立出树的关系就好
安装一个包只要统计 0 到这个点还有没有个没有安装就好先统计最开始有多少1 更新完减去就是这次安装的 ans
卸载的话就是这个子树 1的个数区间修改

树链剖分 题型总结一

树链剖分模板题

P2146 [NOI2015]软件包管理器

全站热榜

树链剖分题型总结一