题目大意 :
有 n 个城市连成一棵树, 每个城市有两个关键字, 一个是该城市的宗教, 另一个是城市的评级;
旅行者要在城市间旅行, 他只会在和自己宗教相同的城市留宿;
维护四个树上操作 {
1. “CC x c“ ：城市 x 的居民全体改信了 c 教；
2. “CW x w“ ：城市 x 的评级调整为 w;
3. “QS x y“ ：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级总和；
4. “QM x y“：一位旅行者从城市 x 出发，到城市 y ，并记下了途中留宿过的城市的评级最大值;
}
(旅行者信的教和旅行的终点相同;
树剖+线段树 : 如果对每种宗教都开一颗线段树, 内存爆炸 -------> 考虑动态开点
动态开点 {
在这道题中, 可以考虑给每一种宗教开一个线段树, 但一开始不需要开满;
对于每一个第一次出现的宗教或者一个宗教里的一个新城市, 都把他当做一个新节点;
对于单次操作 时间复杂度和空间复杂度都是 O(log n) , 因为对于一种宗教最多有n个节点, 在线段树里找到一个节点最多 logn+1 次;
}
代码如下 :
//Author : 15owzLy1
//luogu3313.cpp
//2018 12 09 14:24:30
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 2100000000
typedef long long ll;
typedef double db;
template<typename T>inline void read(T &_) {
_=;int __=;char ___=getchar();
while(___<''||___>'')__|=(___=='-'),___=getchar();
while(___>=''&&___<='')_=(_<<)+(_<<)+(___^),___=getchar();
_=__?-_:_;
} const int N = (int)1e5+;
struct edge {
int next, to;
}edge[N<<];
int head[N], cnt=, c[N], w[N];
int n, q, hson[N], size[N], dfn[N], front[N], dep[N], fa[N]; class Segment_Tree {
private :
struct node {
int sum, max, l, r;
#define t a[rt]
#define lson a[a[rt].l]
#define rson a[a[rt].r]
}a[N*];
int cnt;
inline void push_up(int rt) {
t.sum=lson.sum+rson.sum;
t.max=std::max(lson.max, rson.max);
}
public :
int root[N];
void update(int &rt, int del, int tl, int tr, int pos) {
if(!rt) rt=++cnt;
if(tl==tr) { t.max=t.sum=del; return ; }
int mid=(tl+tr)>>;
if(mid>=pos) update(t.l, del, tl, mid, pos);
else update(t.r, del, mid+, tr, pos);
push_up(rt);
}
void remove(int &rt, int tl, int tr, int pos) {
if(tl==tr) { rt=t.sum=t.max=; return ; }
int mid=(tl+tr)>>;
if(mid>=pos) remove(t.l, tl, mid, pos);
else remove(t.r, mid+, tr, pos);
push_up(rt);
}
int query_sum(int rt, int l, int r, int tl, int tr) {
if(l<=tl&&tr<=r) return t.sum;
int mid=(tl+tr)>>, ret=;
if(mid>=l) ret+=query_sum(t.l, l, r, tl, mid);
if(mid<r) ret+=query_sum(t.r, l, r, mid+, tr);
return ret;
}
int query_max(int rt, int l, int r, int tl, int tr) {
if(l<=tl&&tr<=r) return t.max;
int mid=(tl+tr)>>, ret=;
if(mid>=l) ret=std::max(ret, query_max(t.l, l, r, tl, mid));
if(mid<r) ret=std::max(ret, query_max(t.r, l, r, mid+, tr));
return ret;
}
}T; inline void jb(int u, int v) {
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
} void get_hson(int u) {
size[u]=;
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(v==fa[u]) continue;
fa[v]=u, dep[v]=dep[u]+;
get_hson(v);
size[u]+=size[v];
if(size[v]>=size[hson[u]]) hson[u]=v;
}
} void get_front(int u, int father) {
dfn[u]=++dfn[], front[u]=father;
if(hson[u]) get_front(hson[u], father);
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(v==fa[u]||v==hson[u]) continue;
get_front(v, v);
}
} inline int query_sum(int u, int v) {
int ret=, cl=c[v];
while(front[u]!=front[v]) {
if(dep[front[u]]>dep[front[v]]) std::swap(u, v);
ret+=T.query_sum(T.root[cl], dfn[front[v]], dfn[v], , n);
v=fa[front[v]];
}
if(dep[u]>dep[v]) std::swap(u, v);
ret+=T.query_sum(T.root[cl], dfn[u], dfn[v], , n);
return ret;
} inline int query_max(int u, int v) {
int ret=, cl=c[v];
while(front[u]!=front[v]) {
if(dep[front[u]]>dep[front[v]]) std::swap(u, v);
ret=std::max(ret, T.query_max(T.root[cl], dfn[front[v]], dfn[v], , n));
v=fa[front[v]];
}
if(dep[u]>dep[v]) std::swap(u, v);
ret=std::max(ret, T.query_max(T.root[cl], dfn[u], dfn[v], , n));
return ret;
} int main() {
#ifndef ONLINE_JUDGE
freopen("luogu3313.in","r",stdin);
freopen("luogu3313.out","w",stdout);
#endif
char opt[];
int x, y;
read(n), read(q);
for(int i=;i<=n;i++) read(w[i]), read(c[i]);
for(int i=;i<n;i++) read(x), read(y), jb(x, y), jb(y, x);
get_hson(); get_front(, );
for(int i=;i<=n;i++)
T.update(T.root[c[i]], w[i], , n, dfn[i]); while(q--) {
scanf("%s", opt);
read(x), read(y);
if(opt[]=='C') {
//change C change W
if(opt[]=='C') {
T.remove(T.root[c[x]], , n, dfn[x]);
c[x]=y;
T.update(T.root[c[x]], w[x], , n, dfn[x]);
}
else T.update(T.root[c[x]], y, , n, dfn[x]), w[x]=y;
}
else {
//query S query W
if(opt[]=='S') printf("%d\n", query_sum(x, y));
else printf("%d\n", query_max(x, y));
}
}
return ;
}