听说这是动态开点主席树的板子题，但是发现我还不会，于是就来写一写
其实跟主席树一个样子的
这里就是存个板子吧
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define maxn 100005
struct E
{
int v,nxt;
}e[maxn<<1];
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int head[maxn],deep[maxn],top[maxn],son[maxn],sz[maxn],fa[maxn],to[maxn],b[maxn],c[maxn],a[maxn],_[maxn];
int rt[maxn];
int l[maxn*20],r[maxn*20],sum[maxn*20],d[maxn*20];
int cnt,num,tot,n,Q;
void dfs1(int x)
{
sz[x]=1;
int maxx=-1;
for(re int i=head[x];i;i=e[i].nxt)
if(!deep[e[i].v])
{
deep[e[i].v]=deep[x]+1;
fa[e[i].v]=x;
dfs1(e[i].v);
sz[x]+=sz[e[i].v];
if(sz[e[i].v]>maxx) maxx=sz[e[i].v],son[x]=e[i].v;
}
}
void dfs2(int x,int topf)
{
to[x]=++tot;
b[tot]=a[x];
c[tot]=_[x];
top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(re int i=head[x];i;i=e[i].nxt)
if(deep[e[i].v]>deep[x]&&son[x]!=e[i].v) dfs2(e[i].v,e[i].v);
}
inline void add_edge(int x,int y)
{
e[++num].v=y;
e[num].nxt=head[x];
head[x]=num;
}
int change(int now,int x,int y,int pos,int val)
{
int root=now;
if(!now) root=++cnt;
if(x==y)
{
d[root]=val,sum[root]=val;
return root;
}
int mid=x+y>>1;
if(pos<=mid) l[root]=change(l[root],x,mid,pos,val);
else r[root]=change(r[root],mid+1,y,pos,val);
d[root]=max(d[l[root]],d[r[root]]);
sum[root]=sum[l[root]]+sum[r[root]];
return root;
}
int query(int now,int x,int y,int ll,int rr)
{
if(!now) return 0;
if(ll<=x&&rr>=y) return sum[now];
int mid=x+y>>1;
if(rr<=mid) return query(l[now],x,mid,ll,rr);
if(ll>mid) return query(r[now],mid+1,y,ll,rr);
return query(l[now],x,mid,ll,rr)+query(r[now],mid+1,y,ll,rr);
}
int ask(int now,int x,int y,int ll,int rr)
{
if(!now) return 0;
if(ll<=x&&rr>=y) return d[now];
int mid=x+y>>1;
if(rr<=mid) return ask(l[now],x,mid,ll,rr);
if(ll>mid) return ask(r[now],mid+1,y,ll,rr);
return max(ask(l[now],x,mid,ll,rr),ask(r[now],mid+1,y,ll,rr));
}
inline int ask_sum(int x,int y,int col)
{
int s=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
s+=query(rt[col],1,n,to[top[x]],to[x]);
x=fa[top[x]];
}
if(deep[x]>deep[y]) std::swap(x,y);
s+=query(rt[col],1,n,to[x],to[y]);
return s;
}
inline int ask_max(int x,int y,int col)
{
int s=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) std::swap(x,y);
s=max(s,ask(rt[col],1,n,to[top[x]],to[x]));
x=fa[top[x]];
}
if(deep[x]>deep[y]) std::swap(x,y);
s=max(s,ask(rt[col],1,n,to[x],to[y]));
return s;
}
int main()
{
n=read(),Q=read();
for(re int i=1;i<=n;i++)
{
a[i]=read(),_[i]=read();
if(!rt[_[i]]) rt[_[i]]=++cnt;
}
int x,y;
for(re int i=1;i<n;i++)
x=read(),y=read(),add_edge(x,y),add_edge(y,x);
deep[1]=1,dfs1(1),dfs2(1,1);
for(re int i=1;i<=n;i++)
change(rt[c[i]],1,n,i,b[i]);
char opt[2];
int val;
while(Q--)
{
scanf("%s",opt);
if(opt[0]=='Q'&&opt[1]=='S')
{
x=read(),y=read();
printf("%d
",ask_sum(x,y,_[x]));
}
if(opt[0]=='Q'&&opt[1]=='M')
{
x=read(),y=read();
printf("%d
",ask_max(x,y,_[x]));
}
if(opt[0]=='C'&&opt[1]=='W')
{
x=read(),val=read();
b[to[x]]=val;
change(rt[_[x]],1,n,to[x],val);
}
if(opt[0]=='C'&&opt[1]=='C')
{
x=read(),val=read();
change(rt[val],1,n,to[x],b[to[x]]);
change(rt[_[x]],1,n,to[x],0);
_[x]=val;
}
}
return 0;
}