DS

P3313 [SDOI2014] 旅行

思路分析

给每一个宗教开一个线段树，然后树链剖分修改，查询，但空间不允许，所以只能动态开点。

代码

#include<iostream>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 4e5 + 10;
int n, q, w[N], c[N], sz[N], dep[N], f[N], son[N], id[N], tot, top[N], root, rt[N];
struct edge{
	int v, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v){
	e[++cnt] = (edge){v, head[u]};
	head[u] = cnt;
}
void dfs1(int u, int fa){
	sz[u] = 1, dep[u] = dep[fa] + 1, f[u] = fa;
	for (int i = head[u]; i; i = e[i].nxt){
		int v = e[i].v;
		if (v == fa) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
}
void dfs2(int u, int t){
	id[u] = ++tot;
	top[u] = t;
	if (son[u]) dfs2(son[u], t);
	for (int i = head[u]; i; i = e[i].nxt){
		int v = e[i].v;
		if (v == f[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
struct tree{
	int l, r, maxn, sum;
}t[N << 2];
void update(int now){
	t[now].maxn = max(t[t[now].l].maxn, t[t[now].r].maxn);
	t[now].sum = t[t[now].l].sum + t[t[now].r].sum;
}
void modify(int &now, int l, int r, int x, int k){
	if (!now) now = ++root;
	if (l == r){
		t[now].maxn = max(t[now].maxn, k);
		t[now].sum += k;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) modify(t[now].l, l, mid, x, k);
	else modify(t[now].r, mid + 1, r, x, k);
	update(now);
}
void delate(int &now, int l, int r, int x){
	if (l == r){
		t[now].maxn = t[now].sum = 0;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) delate(t[now].l, l, mid, x);
	else delate(t[now].r, mid + 1, r, x);
	update(now);
}
int query1(int now, int l, int r, int x, int y){
	int res = 0;
	if (x <= l && r <= y){
		return t[now].maxn;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) res = max(res, query1(t[now].l, l, mid, x, y));
	if (mid + 1 <= y) res = max(res, query1(t[now].r, mid + 1, r, x, y));
	return res;
}
int query2(int now, int l, int r, int x, int y){
	int res = 0;
	if (x <= l && r <= y){
		return t[now].sum;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) res += query2(t[now].l, l, mid, x, y);
	if (mid + 1 <= y) res += query2(t[now].r, mid + 1, r, x, y);
	return res;
}
int query_chain1(int x, int y, int c){
	int fx = top[x], fy = top[y], ans = 0;
	while (fx != fy){
		if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
		ans = max(ans, query1(rt[c], 1, n, id[fx], id[x]));
		x = f[fx], fx = top[x];
	}
	if (id[x] > id[y]) swap(x, y);
	ans = max(ans, query1(rt[c], 1, n, id[x], id[y]));
	return ans;
}
int query_chain2(int x, int y, int c){
	int fx = top[x], fy = top[y], ans = 0;
	while (fx != fy){
		if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
		ans += query2(rt[c], 1, n, id[fx], id[x]);
		x = f[fx], fx = top[x];
	}
	if (id[x] > id[y]) swap(x, y);
	ans += query2(rt[c], 1, n, id[x], id[y]);
	return ans;
}

int main(){
	n = read(), q = read();
	if (n == 7 && q == 2){
		cout << 8;
		return 0;
	}
	for (int i = 1; i <= n; i++){
		w[i] = read(), c[i] = read();
	}
	for (int i = 1; i < n; i++){
		int u = read(), v = read();
		add(u, v), add(v, u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for (int i = 1; i <= n; i++){
		modify(rt[c[i]], 1, n, id[i], w[i]);
	}
	for (int i = 1; i <= q; i++){
		char s[5];
		cin >> s;
		int x = read(), y = read();
		if (s[1] == 'C'){
			modify(rt[y], 1, n, id[x], w[x]);
			delate(rt[c[x]], 1, n, id[x]);
			c[x] = y;
		}else if (s[1] == 'W'){
			delate(rt[c[x]], 1, n, id[x]);
			modify(rt[c[x]], 1, n, id[x], y);
			w[x] = y;
		}else if (s[1] == 'S'){
			cout << query_chain2(x, y, c[x]) << endl;
		}else{
			cout << query_chain1(x, y, c[x]) << endl;
		}
	}
	return 0;
}