题目大意
给定一颗树与一些集合。树上的每个结点一开始都属于一个集合，且都拥有一个点权。定义 \(C_x\) 表示 \(x\) 结点所处的集合。
维护一些操作：
- 将结点 \(x\) 改到 \(c\) 集合中。
- 将结点 \(x\) 的权值改为 \(w\)。
- 求出 \(x\) 到 \(y\) 链上所有位于 \(C_x\) 的结点点权最大值。
- 求出 \(x\) 到 \(y\) 链上所有位于 \(C_x\) 的结点点权之和。
\(n,q,c\leq 10^5\)
思路
考虑树链剖分。树链剖分可以用来维护链/子树的操作。定义一个结点的重儿子表示它的子儿子的子树大小最大的一个，如果有多个则任取一个。
之后将重儿子移到当前结点的第一个儿子，之后得出新的 \(dfn\) 序。之后的树链剖分就可以找到每一条链上最长的重儿子链，然后对这些链进行维护。可以证明每一次经过的链是 \(\log n\) 级别的，之后用线段树什么的维护序列即可。
对于本题，我们可以建 \(c\) 颗动态开点线段树去维护每一个集合的信息。如果 \(C_x\) 不属于当前的线段树直接把对应位置赋值为 \(0\) 即可。
时间复杂度 \(O(n\log_2^2 n)\)，空间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
#define lc(u) t[u].l
#define rc(u) t[u].r
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll n,q;
ll w[MAXN],c[MAXN];
vector<ll>adj[MAXN];
ll tot,sz[MAXN],dfn[MAXN],id[MAXN],cs[MAXN],fa[MAXN],dep[MAXN],hs[MAXN];
void dfs(ll u,ll f,ll d){
dep[u]=d;
fa[u]=f;
sz[u]=1;
for(auto v:adj[u]){
if(v==f){
continue;
}
dfs(v,u,d+1);
sz[u]+=sz[v];
if(!hs[u]||sz[hs[u]]<sz[v]){
hs[u]=v;
}
}
}
void dfs_divide(ll u,ll start){
cs[u]=start;
dfn[++tot]=u;
id[u]=tot;
if(hs[u]==0){
return;
}
dfs_divide(hs[u],start);
for(auto v:adj[u]){
if(v==fa[u]||v==hs[u]){
continue;
}
dfs_divide(v,v);
}
}
struct node{
ll u,val,ma,l,r;
}t[10000000];
ll nt=MAXN;
void push_up(ll u){
t[u].val=t[lc(u)].val+t[rc(u)].val;
t[u].ma=max(t[lc(u)].ma,t[rc(u)].ma);
}
void change(ll &u,ll l,ll r,ll pos,ll x){
if(!u){
u=++nt;
}
if(l==r){
t[u].val=t[u].ma=x;
return;
}
ll mid=(l+r)>>1;
if(pos<=mid){
change(lc(u),l,mid,pos,x);
}else{
change(rc(u),mid+1,r,pos,x);
}
push_up(u);
}
ll query1(ll u,ll l,ll r,ll ql,ll qr){
if(!u){
return 0;
}
if(ql<=l&&r<=qr){
return t[u].val;
}
ll mid=(l+r)>>1,ans=0;
if(ql<=mid){
ans+=query1(lc(u),l,mid,ql,qr);
}
if(mid+1<=qr){
ans+=query1(rc(u),mid+1,r,ql,qr);
}
return ans;
}
ll query2(ll u,ll l,ll r,ll ql,ll qr){
if(!u){
return 0;
}
if(ql<=l&&r<=qr){
return t[u].ma;
}
ll mid=(l+r)>>1,ans=0;
if(ql<=mid){
ans=query2(lc(u),l,mid,ql,qr);
}
if(mid+1<=qr){
ans=max(ans,query2(rc(u),mid+1,r,ql,qr));
}
return ans;
}
ll qs(ll u,ll v,ll C){
ll ans=0;
while(cs[u]!=cs[v]){
if(dep[cs[u]]<dep[cs[v]]){
swap(u,v);
}
ans+=query1(C,1,n,id[cs[u]],id[u]);
u=fa[cs[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
return ans+query1(C,1,n,id[u],id[v]);
}
ll qm(ll u,ll v,ll C){
ll ans=0;
while(cs[u]!=cs[v]){
if(dep[cs[u]]<dep[cs[v]]){
swap(u,v);
}
ans=max(ans,query2(C,1,n,id[cs[u]],id[u]));
u=fa[cs[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
return max(ans,query2(C,1,n,id[u],id[v]));
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>w[i]>>c[i];
}
for(int i=1;i<n;++i){
ll x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1,0,1);
dfs_divide(1,1);
for(int i=1;i<=n;++i){
change(c[i],1,n,id[i],w[i]);
}
while(q--){
string op;
cin>>op;
if(op=="CC"){
ll x,nc;
cin>>x>>nc;
change(c[x],1,n,id[x],0);
c[x]=nc;
change(c[x],1,n,id[x],w[x]);
}else if(op=="CW"){
ll x,nw;
cin>>x>>nw;
w[x]=nw;
change(c[x],1,n,id[x],w[x]);
}else if(op=="QS"){
ll x,y;
cin>>x>>y;
cout<<qs(x,y,c[x])<<endl;
}else if(op=="QM"){
ll x,y;
cin>>x>>y;
cout<<qm(x,y,c[x])<<endl;
}
}
return 0;
}