树链剖分 题型总结一

树链剖分模板题

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

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

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

这样的话 重路 最多lg 个， 线树维护复杂度 也是lg的 这样总复杂度是 $l{g}^{2}n$lg2n的
洛谷树链剖分模板题 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的个数 区间修改

#include <bits/stdc++.h>
#define debug(x, str) cout << (str) << " = [ << : " << (x) << " ]" << endl;
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], 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;
	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]);
}

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

void build(int l, int r, int rt) {
	lazy[rt] = -1, tree[rt] = 0;
	if(l == r) 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] = (val * (r - l + 1));
		lazy[rt] = val;
		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));
	if(R > mid) res = (res +query(L, R, mid + 1, r, rt << 1 | 1));
	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) {
	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));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = (ret + query(dfn[x], dfn[y], 1, n, 1));
	return ret;
}

signed main() {
	scanf("%d", &n);
	for(int i = 1, b; i < n; ++ i) {
		scanf("%d", &b);
		ade(b ,i), ade(i, b);
	}
	dfs1(0, -1);
	dfs2(0, -1);
	build(1, n, 1);
	scanf("%d", &m);
	int id;
	char op[15];
	while(m --) {
		scanf("%s %d", op, &id);
		if(op[0] == 'i') {
			int ans;
			ans = qchain(0, id);
			mchain(0, id, 1);
			ans = qchain(0, id) - ans;
			printf("%d\n", ans);
		} else {
			printf("%d\n", qson(id));
			mson(id, 0);
		}
	}
	return 0;
}