题目描述
S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。
为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
“CC x c“：城市x的居民全体改信了c教；
“CW x w“：城市x的评级调整为w;
“QS x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
“QM x y“：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
输入输出格式
输入格式：
输入的第一行包含整数N，Q依次表示城市数和事件数。 接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的评级和信仰。 接下来N-1行每行两个整数x，y表示一条双向道路。 接下来Q行，每行一个操作，格式如上所述。
输出格式：
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
输入输出样例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
5 6 3 1 2 3 1 2 3 3 5 1 1 2 1 3 3 4 3 5 QS 1 5 CC 3 1 QS 1 5 CW 3 3 QS 1 5 QM 2 4 |
说明
N，Q < =10^5 ， C < =10^5
数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时
刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。
首先想到的就是线段树+树链剖分
不过怎么维护宗教值呢？
可以对每个宗教开一个线段树，也就是开c个线段树
修改宗教值就是先在所属宗教的线段树将其评级变为0，再在改后所属宗教的线段树将评级改变
因为C比较大，可以采取动态开点的方法，空间复杂度O(qlogn)
（手残把l打成1查了一小时BUG才发现，rua！
|
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 |
#include<stdio.h> #include<iostream> #include<string.h> #define max(a, b) ((a) > (b) ? (a) : (b)) #define MAXN 100010 using namespace std; struct Edge { int u, v, next; } e[2*MAXN]; struct node { int lc, rc, s, m; } t[50*MAXN]; int n, Q, cnt, tot, h[MAXN], top[MAXN], son[MAXN], dep[MAXN], w[MAXN], par[MAXN], id[MAXN], a[MAXN], c[MAXN], rt[MAXN]; char opt[5]; void addEdge(int u, int v, int num) { e[num] = (Edge) {u, v, h[u]}; h[u] = num; } void dfs(int u) { w[u] = 1; for (int i = h[u]; i; i = e[i].next) { if (!w[e[i].v]) { par[e[i].v] = u; dep[e[i].v] = dep[u]+1; dfs(e[i].v); w[u] += w[e[i].v]; if (w[son[u]] < w[e[i].v]) son[u] = e[i].v; } } } void init(int u, int p) { top[u] = p; id[u] = ++cnt; if (son[u]) init(son[u], p); for (int i = h[u]; i; i = e[i].next) { if (!top[e[i].v]) init(e[i].v, e[i].v); } } void modify(int l, int r, int x, int y, int d, int &p) { if (!p) p = ++tot; if (x <= l && r <= y) { t[p].s = t[p].m = d; } else { int mid = (l+r)>>1; if (x <= mid) modify(l, mid, x, y, d, t[p].lc); if (y > mid) modify(mid+1, r, x, y, d, t[p].rc); t[p].s = t[t[p].lc].s+t[t[p].rc].s; t[p].m = max(t[t[p].lc].m, t[t[p].rc].m); } } int query(int l, int r, int x, int y, int o, int &p) { if (x <= l && r <= y) { if (!o) return t[p].s; return t[p].m; } int mid = (l+r)>>1, t1 = 0, t2 = 0; if (x <= mid) t1 = query(l, mid, x, y, o, t[p].lc); if (y > mid) t2 = query(mid+1, r, x, y, o, t[p].rc); if (!o) return t1+t2; return max(t1, t2); } int solve(int u, int v, int col, int o) { int pu = top[u], pv = top[v], sum = 0, mx = 0, tmp; while (pu != pv) { if (dep[pu] < dep[pv]) { swap(u, v); swap(pu, pv); } tmp = query(1, n, id[pu], id[u], o, rt[col]); if (!o) sum += tmp; else mx = max(mx, tmp); u = par[pu]; pu = top[u]; } if (dep[u] > dep[v]) swap(u, v); tmp = query(1, n, id[u], id[v], o, rt[col]); if (!o) return sum+tmp; return max(mx, tmp); } int main() { scanf("%d%d", &n, &Q); for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &c[i]); for (int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); addEdge(u, v, i); addEdge(v, u, i+n); } dep[1] = 1; dfs(1); init(1, 1); for (int i = 1; i <= n; ++i) { modify(1, n, id[i], id[i], a[i], rt[c[i]]); } for (int i = 1, u, v; i <= Q; ++i) { scanf("%s%d%d", opt, &u, &v); if (opt[1] == 'C') { modify(1, n, id[u], id[u], 0, rt[c[u]]); c[u] = v; modify(1, n, id[u], id[u], a[u], rt[c[u]]); } else if (opt[1] == 'W') { a[u] = v; modify(1, n, id[u], id[u], a[u], rt[c[u]]); } else if (opt[1] == 'S') { printf("%d\n", solve(u, v, c[u], 0)); } else if (opt[1] == 'M') { printf("%d\n", solve(u, v, c[u], 1)); } } return 0; } |