[树链剖分] P3313 [SDOI2014]旅行(动态开点 线段树)

P3313 [SDOI2014]旅行

https://www.luogu.org/problem/P3313
我们 单点修改城市的信仰 和 开销
询问 路径上 同信仰的城市 开销的花费和 or路径上最大值
显然 我们树链剖分完 直接建立 1e5 颗线段树 是最方便的 而且是单点修改 确保了我们时间上 和空间上的复杂度保证
我们考虑动态开点 来降低内存上的开销
注意细节。我在查询最大值 sum时 没有lc rc 我直接retrun 了 跳过了 后半区间的 值 orz。要注意细节orz 这bug 是我洗完澡回来重新看自己代码发现的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, k, m;
int head[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1];
int buff[maxn], ctma[maxn];
void ade(int a, int b) {
	to[++ cnt] = b;
	nxt[cnt] = head[a], head[a] = cnt;
}

int siz[maxn], son[maxn], fa[maxn], dep[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], bel[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);
	}
}

struct node{
	int lc, rc, sum, ma;
}tr[maxn * 20];
int root[maxn], tot;

int build() {
	++ tot;
	tr[tot].lc = tr[tot].rc = tr[tot].sum = tr[tot].ma = 0;
	return tot;
}

void push_up(int rt) {
	tr[rt].sum = tr[tr[rt].lc].sum + tr[tr[rt].rc].sum;
	tr[rt].ma = max(tr[tr[rt].lc].ma, tr[tr[rt].rc].ma);
}

void insert(int p, int L, int l, int r, int val) {
	if(l == r) {
		tr[p].ma = tr[p].sum = val;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) {
		if(!tr[p].lc) tr[p].lc = build();
		insert(tr[p].lc, L , l, mid, val);
	} else {
		if(!tr[p].rc) tr[p].rc = build();
		insert(tr[p].rc, L, mid + 1, r, val);
	}
	push_up(p);
}

int querymax(int p, int L, int R, int l, int r) {
	if(L <= l && r <= R) return tr[p].ma;
	int mid = l + r >> 1;
	int res = 0;
	if(L <= mid) {
		if(!tr[p].lc) res = max(res, 0); 
		else res = max(res, querymax(tr[p].lc, L, R, l, mid));
	}
	if(R > mid) {
		if(!tr[p].rc) res = max(res, 0);
		else res = max(res, querymax(tr[p].rc, L, R, mid + 1, r));
	}
	return res;
}

int querysum(int p, int L, int R, int l, int r) {
	if(L <= l && r <= R) return tr[p].sum;
	int mid = l + r >> 1;
	int res = 0;
	if(L <= mid) {
		if(!tr[p].lc) res = res; 
		else res = (res + querysum(tr[p].lc, L, R, l, mid));
	}
	if(R > mid) {
		if(!tr[p].rc) res = res;
		else res = (res + querysum(tr[p].rc, L, R, mid + 1, r));
	}
	return res;
}

int qsumchain(int buff, int x, int y) {
	int ret = 0;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = (ret + querysum(root[buff], dfn[top[x]], dfn[x], 1, n));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = (ret + querysum(root[buff], dfn[x], dfn[y], 1, n)); 
	return ret;
}

int qmaxchain(int buff, int x, int y) {
	int ret = 0;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y);
		ret = max(ret, querymax(root[buff], dfn[top[x]], dfn[x], 1, n));
		x = fa[top[x]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	ret = max(ret, querymax(root[buff], dfn[x], dfn[y], 1, n)); 
	return ret;
}

signed main() {
	scanf("%d %d", &n, &m);
	tot = 0;
	for(int i = 1; i <= n; i ++) root[i] = build();
	for(int i = 1; i <= n; i ++) {
		scanf("%d %d", &ctma[i], &buff[i]);
	}
	for(int i = 1, a, b; i < n; i ++) {
		scanf("%d %d", &a, &b);
		 ade(a, b), ade(b, a);
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for(int i = 1; i <= n; i ++) {
		if(!root[buff[i]]) root[buff[i]] = build();
		insert(root[buff[i]], dfn[i], 1, n, ctma[i]);
	}
	char op[15]; int x, y;
	while(m --) {
		scanf("%s %d %d", op, &x, &y);
		int buffs = buff[x];
		if(op[1] =='C') {
			insert(root[buffs], dfn[x], 1, n, 0);
			if(!root[y]) root[y] = build(); 
			buff[x] = y;
			insert(root[y], dfn[x], 1, n, ctma[x]);
		} else if(op[1] == 'W') {
			ctma[x] = y;
			insert(root[buffs], dfn[x], 1, n, ctma[x]);
		} else if(op[1] == 'S') {
			printf("%d\n", qsumchain(buffs, x, y));
		} else if(op[1] == 'M') {
			printf("%d\n", qmaxchain(buffs, x, y));
		}
	}
	return 0;
}