传送门
树剖+动态开点线段树
对每种宗教开一个线段树，用来维护区间和，区间最大值
普通的线段树空间不够，所以要动态开点
因为宗教会改变，所以要有删除操作和插入操作
比如城市1从信仰a变成信仰b，那就把a的线段树上城市1删掉，在b线段树上插入城市1
询问就只要询问与旅行者同宗教的值就好了
怎么实现也不难，看看代码就懂了
然后我还搞了个垃圾回收的操作
把删掉的节点编号记录一下，如果有新增节点，编号优先用以前的
很容易实现
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; }const int N=2e5+7; int n,m,w[N],c[N];int fir[N<<1],from[N<<1],to[N<<1],cntt; inline void add(int &a,int &b) {from[++cntt]=fir[a];fir[a]=cntt; to[cntt]=b; }//以下为树剖预处理 int dep[N],sz[N],fa[N],son[N]; void dfs1(int x,int f) {dep[x]=dep[f]+1; sz[x]=1; fa[x]=f;int mxsz=0;for(int i=fir[x];i;i=from[i]){int &v=to[i];if(v==f) continue;dfs1(v,x); sz[x]+=sz[v];if(sz[v]>mxsz)mxsz=sz[v],son[x]=v;} } int id[N],Top[N],tot; void dfs2(int x,int topp) {id[x]=++tot; Top[x]=topp;if(!son[x]) return;dfs2(son[x],topp);for(int i=fir[x];i;i=from[i]){int &v=to[i];if(v==fa[x]||v==son[x]) continue;dfs2(v,v);} } //以上为树剖预处理//--------------------------线段树---------------------------------- struct node {int sum,mx,lc,rc;//因为动态开点所以要记录左右儿子node() { sum=mx=lc=rc=0; } }t[N<<4]; int cnt,rt[N];//rt是每个宗教的根节点 queue <int> q;//存回收的编号 inline void pushup(int &o)//更新当前节点 {t[o].sum=t[t[o].lc].sum+t[t[o].rc].sum;t[o].mx=max(t[t[o].lc].mx,t[t[o].rc].mx); } inline void clr(int &o)//回收垃圾 {t[o].sum=t[o].mx=t[o].lc=t[o].rc=0;q.push(o); o=0; } void ins(int &o,int l,int r,int &v/*值*/,int &pos/*位置*/)//插入 or 更新 {if(!o)//如果还没节点就新建一个 {if(!q.empty()) o=q.front(),q.pop();//垃圾回收利用else o=++cnt;}if(l==r)//如果到叶子节点就更新并返回 {t[o].sum=t[o].mx=v;return;}int mid=l+r>>1;if(pos<=mid) ins(t[o].lc,l,mid,v,pos);else ins(t[o].rc,mid+1,r,v,pos);pushup(o);//更新当前节点 } void erase(int &o,int l,int r,int &pos)//删除 {if(l==r) { clr(o); return; }int mid=l+r>>1;if(pos<=mid) erase(t[o].lc,l,mid,pos);else erase(t[o].rc,mid+1,r,pos);if(t[o].lc||t[o].rc) pushup(o);//如果还有儿子就更新值else clr(o);//不然一起删了 } int query_sum(int o,int l,int r,int &ql,int &qr)//询问区间sum {if(!o) return 0;if(l>=ql&&r<=qr) return t[o].sum;int mid=l+r>>1,res=0;if(ql<=mid) res+=query_sum(t[o].lc,l,mid,ql,qr);if(qr>mid) res+=query_sum(t[o].rc,mid+1,r,ql,qr);return res; } int query_max(int o,int l,int r,int &ql,int &qr)//询问区间max {if(!o) return 0;if(l>=ql&&r<=qr) return t[o].mx;int mid=l+r>>1,res=0;if(ql<=mid) res=max(res,query_max(t[o].lc,l,mid,ql,qr));if(qr>mid) res=max(res,query_max(t[o].rc,mid+1,r,ql,qr));return res; } //----------------------------线段树----------------------------------void change_bel(int x,int y)//改变信仰 {erase(rt[c[x]],1,n,id[x]);c[x]=y;ins(rt[c[x]],1,n,w[x],id[x]); } void change_val(int x,int y)//改变价值 {w[x]=y;ins(rt[c[x]],1,n,w[x],id[x]); }void Q_sum(int x,int y)//询问树上两点间路径的同宗教的sum {int res=0,be=c[x];//旅行者的宗教while(Top[x]!=Top[y])//正常的树剖询问 {if(dep[Top[x]]<dep[Top[y]]) swap(x,y);res+=query_sum(rt[be],1,n,id[Top[x]],id[x]);x=fa[Top[x]];}if(dep[x]<dep[y]) swap(x,y);res+=query_sum(rt[be],1,n,id[y],id[x]);printf("%d\n",res); } void Q_max(int x,int y)//跟上面差不多 {int res=0,be=c[x];while(Top[x]!=Top[y]){if(dep[Top[x]]<dep[Top[y]]) swap(x,y);res=max(res,query_max(rt[be],1,n,id[Top[x]],id[x]));x=fa[Top[x]];}if(dep[x]<dep[y]) swap(x,y);res=max(res,query_max(rt[be],1,n,id[y],id[x]));printf("%d\n",res); }int main() {n=read(); m=read();for(int i=1;i<=n;i++) w[i]=read(),c[i]=read();int a,b;for(int i=1;i<n;i++) a=read(),b=read(),add(a,b),add(b,a);dfs1(1,1); dfs2(1,1);for(int i=1;i<=n;i++) ins(rt[c[i]],1,n,w[i],id[i]);//处理好初始状态char ch[5];for(int i=1;i<=m;i++){scanf("%s",ch); a=read(); b=read();if(ch[0]=='C'){if(ch[1]=='C') change_bel(a,b);else change_val(a,b);}else{if(ch[1]=='S') Q_sum(a,b);else Q_max(a,b);}}return 0; }