Description
一棵树支持以下操作。
修改颜色，修改权值。
问(x,y)路径上与(x)同色中最大值，和。
Solution
树链剖分。
对于每个颜色建一个动态开点的线段树即可。
Code
/**************************************************************
Problem: 3531
User: BeiYu
Language: C++
Result: Accepted
Time:11060 ms
Memory:44876 kb
****************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define mpr make_pair
#define x first
#define y second
#define debug(a) cout<<(#a)<<"="<<a<<" "
#define lc(o) ch[o][0]
#define rc(o) ch[o][1]
#define mid ((l+r)>>1)
typedef long long LL;
typedef pair<int,int> pr;
typedef vector<int> Vi;
typedef vector<LL> Vl;
typedef vector<string> Vs;
const int N = 100050;
const int M = N*20;
const int oo = 0x3fffffff;
const LL OO = 1e18;
void chkmax(int &x,int y) { if(x<y) x=y; }
inline LL in(LL x=0,char ch=getchar(),int v=1) {
while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*v;
}
/*end*/
int n,q;
int w[N],c[N],rt[N],p[N];
namespace Seg {
int cnt;
int ch[M][2],mx[M],s[M];
int NewNode() {
++cnt;lc(cnt)=rc(cnt)=mx[cnt]=s[cnt]=0;
return cnt;
}
void Update(int o) {
mx[o]=s[o]=0;
if(lc(o)) chkmax(mx[o],mx[lc(o)]),s[o]+=s[lc(o)];
if(rc(o)) chkmax(mx[o],mx[rc(o)]),s[o]+=s[rc(o)];
}
void Modify(int &o,int l,int r,int x,int v) {
if(!o) o=NewNode();
if(l==r) { mx[o]=s[o]=v;return; }
if(x<=mid) Modify(lc(o),l,mid,x,v);
else Modify(rc(o),mid+1,r,x,v);
Update(o);
}
int QueryMax(int o,int l,int r,int L,int R) {
if(!o) return 0;
if(L<=l && r<=R) return mx[o];
int res=0;
if(L<=mid) chkmax(res,QueryMax(lc(o),l,mid,L,R));
if(R>mid) chkmax(res,QueryMax(rc(o),mid+1,r,L,R));
return res;
}
int QuerySum(int o,int l,int r,int L,int R) {
if(!o) return 0;
if(L<=l && r<=R) return s[o];
int res=0;
if(L<=mid) res+=QuerySum(lc(o),l,mid,L,R);
if(R>mid) res+=QuerySum(rc(o),mid+1,r,L,R);
return res;
}
}
namespace Tree {
int cnt;
int top[N],f[N],sz[N],sn[N],dep[N];
vector<int> g[N];
void AddEdge(int u,int v) { g[u].push_back(v),g[v].push_back(u); }
void DFS1(int x,int fa) {
sz[x]=1,sn[x]=0,dep[x]=dep[fa]+1;
for(int i=0,v;i<(int)g[x].size();i++) if((v=g[x][i])!=fa) {
DFS1(v,x),sz[x]+=sz[v],f[v]=x;
if(!sn[x] || sz[v]>sz[sn[x]]) sn[x]=v;
}
}
void DFS2(int x,int fa,int tp) {
p[x]=++cnt,top[x]=tp;
if(sn[x]) DFS2(sn[x],x,tp);
for(int i=0,v;i<(int)g[x].size();i++) if((v=g[x][i])!=fa && v!=sn[x])
DFS2(v,x,v);
}
void init() {
DFS1(1,1);
DFS2(1,1,1);
for(int i=1;i<=n;i++) Seg::Modify(rt[c[i]],1,n,p[i],w[i]);
}
int QueryMax(int u,int v) {
int f1=top[u],f2=top[v],res=0,cc=c[u];
for(;f1^f2;) {
if(dep[f1]<dep[f2]) swap(u,v),swap(f1,f2);
chkmax(res,Seg::QueryMax(rt[cc],1,n,p[f1],p[u]));
u=f[f1],f1=top[u];
}if(dep[u]>dep[v]) swap(u,v);
chkmax(res,Seg::QueryMax(rt[cc],1,n,p[u],p[v]));
return res;
}
int QuerySum(int u,int v) {
int f1=top[u],f2=top[v],res=0,cc=c[u];
for(;f1^f2;) {
if(dep[f1]<dep[f2]) swap(u,v),swap(f1,f2);
res+=Seg::QuerySum(rt[cc],1,n,p[f1],p[u]);
u=f[f1],f1=top[u];
}if(dep[u]>dep[v]) swap(u,v);
res+=Seg::QuerySum(rt[cc],1,n,p[u],p[v]);
return res;
}
}
int main() {
n=in(),q=in();
for(int i=1;i<=n;i++) w[i]=in(),c[i]=in();
for(int i=1;i<n;i++) {
int u=in(),v=in();
Tree::AddEdge(u,v);
}
Tree::init();
for(;q--;) {
char opt[15];
scanf("%s",opt);
int x=in(),y=in();
switch(opt[1]) {
case 'C':
Seg::Modify(rt[c[x]],1,n,p[x],0),c[x]=y;
Seg::Modify(rt[c[x]],1,n,p[x],w[x]);break;
case 'W':Seg::Modify(rt[c[x]],1,n,p[x],y),w[x]=y;break;
case 'S':printf("%d
",Tree::QuerySum(x,y));break;
default:printf("%d
",Tree::QueryMax(x,y));break;
}
}return 0;
}