哈哈哈哈没想到居然会是第一道动态开点线段树
之前一直想学，模板还没调过，结果在这里遇到了
题解：
有个很朴素的想法是对每个宗教开一棵线段树
但是这样1e5*1e5，空间会炸
考虑像主席树那样动态开点，需要的时候再开辟新节点，显然新增的节点不会很多
开辟新节点也很简单:
if(ql<=mid) { if(!ls[rt]) {ls[rt]=++idx;} update(ls[rt],l,mid,ql,qr,reli,w); } if(mid<qr) { if(!rs[rt]) {rs[rt]=++idx;} update(rs[rt],mid+1,r,ql,qr,reli,w); }
再开个数组rt[]记录一下每个宗教根节点的位置
然后就是树链剖分完，线段树维护求和，以及最大值了
ps:
有个憨憨，改信一个宗教——没把原来的删除
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; const int maxn=2*int(1e5)+7; ll cnt=0,ecnt=0; ll n,m,R,id[maxn],wt[maxn],top[maxn],son[maxn],head[maxn],fa[maxn],siz[maxn],dep[maxn]; struct lys{ int from,to,nex; }e[maxn*2]; void addedge(int from,int to){ ecnt++;e[ecnt].from=from;e[ecnt].to=to;e[ecnt].nex=head[from];head[from]=ecnt; } void dfs1(int u,int f){ siz[u]=1; fa[u]=f; dep[u]=dep[f]+1; int maxson=-1; for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==f) continue; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>maxson) son[u]=to,maxson=siz[to]; } } void dfs2(int u,int topf){ cnt++;// dfs order id[u]=cnt; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==son[u]||to==fa[u]) continue; dfs2(to,to); } } // seg tree int idx,a[maxn*40],mx[maxn*40],ls[maxn*40],rs[maxn*40],rt[maxn*40]; int w[maxn],c[maxn]; void push_up(int rt){ a[rt]=a[ls[rt]]+a[rs[rt]]; mx[rt]=max(mx[ls[rt]],mx[rs[rt]]); } void update(int rt,int l,int r,int ql,int qr,int reli,int w){ if(ql<=l&&r<=qr){ a[rt]=w; mx[rt]=w; return; } int mid=(l+r)>>1; if(ql<=mid) { if(!ls[rt]) {ls[rt]=++idx;} update(ls[rt],l,mid,ql,qr,reli,w); } if(mid<qr) { if(!rs[rt]) {rs[rt]=++idx;} update(rs[rt],mid+1,r,ql,qr,reli,w); } push_up(rt); } //add(1,1,n,id[x],id[y],k); ll querySum(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return a[rt]; } int mid=(l+r)>>1; ll ans=0; if(mid>=ql) ans+=querySum(ls[rt],l,mid,ql,qr); if(mid<qr) ans+=querySum(rs[rt],mid+1,r,ql,qr); return ans; } ll queryMax(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return mx[rt]; } int mid=(l+r)>>1; ll ans=0; if(mid>=ql) ans=max(ans,queryMax(ls[rt],l,mid,ql,qr)); if(mid<qr) ans=max(ans,queryMax(rs[rt],mid+1,r,ql,qr)); return ans; } pair<ll,ll> qpath(int x,int y){ ll ans=0; ll maxn=0; int C=c[x]; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=querySum(rt[C],1,n,id[top[x]],id[x]); maxn=max(maxn,queryMax(rt[C],1,n,id[top[x]],id[x])); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=querySum(rt[C],1,n,id[x],id[y]); maxn=max(maxn,queryMax(rt[C],1,n,id[x],id[y])); return make_pair(ans,maxn); } int main(){ //freopen("lys.in","r",stdin); fastio; cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]; for(int i=1;i<n;i++){ int a,b;cin>>a>>b;addedge(a,b);addedge(b,a); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=n;i++){ if(!rt[c[i]]) rt[c[i]]=++idx; update(rt[c[i]],1,n,id[i],id[i],c[i],w[i]); } for(int i=1;i<=m;i++){ string s;cin>>s; if(s=="CC") { int x,C;cin>>x>>C; update(rt[c[x]],1,n,id[x],id[x],0,0); if(!rt[C]) rt[C]=++idx; c[x]=C; update(rt[c[x]],1,n,id[x],id[x],c[x],w[x]); } if(s=="CW"){ int x,W;cin>>x>>W; w[x]=W; update(rt[c[x]],1,n,id[x],id[x],c[x],w[x]); } if(s=="QS"){ int x,y;cin>>x>>y; pair<ll,ll>g=qpath(x,y); cout<<g.first<<endl; } if(s=="QM"){ int x,y;cin>>x>>y; pair<ll,ll>g=qpath(x,y); cout<<g.second<<endl; } } }