题目描述
把题目中的宗教称为类型,评级称为权值,那么题意大意就是要实现树上的四种操作:
1.改变某个点的类型
2.改变某个点的权值
3.查询树上一条路径上的与起点类型相同的点的权值和
4.查询树上一条路径上的与起点类型相同的点中最大的权值
可以考虑用树链剖分得到一个序列,然后狠狠用分块暴力的做,每一块内统计所有类型的权值和与最大权值,修改时就直接暴力重构这一整个块,由于acwing上这题给的内存只有64MB,所以要考虑牺牲一部分速度来让块数减少一点来减少内存消耗,这里块长len=sqrt(1.7nlog2(n))+1(直接取n=sqrt(n)可以跑的很快,在某谷上跑的好像比权值线段树快一点)。
时间复杂度
O(n^(3/2)log(n))
C++ 代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<string>
using namespace std;
#define ls(u) tr[u].son[0]
#define rs(u) tr[u].son[1]
const int N=1e5+505,M=2*N,L=70,INF=0x3f3f3f3f,mod=998244353;
const double alpha=0.725,eps=1e-8;
typedef long long LL;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=0,f=1;char ch=nc();
while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
if(ch=='-')f=-1;
while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch^48),ch=nc();
return f*x;
}
int pt;
inline void read(char* opt){
char ch=nc();
while(ch<65||ch>132||ch>90&&ch<97)ch=nc();
while(ch>=65&&ch<=90||ch>=97&&ch<=132||ch=='-')opt[pt++]=ch,ch=nc();
opt[pt]=0,pt=0;
}
int n,m,h[N],e[M],ne[M],idx,v[N],c[N];
int fa[N],sz[N],depth[N],son[N];
int q[N],top[N],id[N],tot;
inline void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
//树链剖分:
inline void dfs1(int u,int p){
sz[u]=1,depth[u]=depth[p]+1,fa[u]=p;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==p)continue;
dfs1(j,u);
sz[u]+=sz[j];
if(sz[j]>sz[son[u]])son[u]=j;
}
}
inline void dfs2(int u,int p,int t){
q[++tot]=u,id[u]=tot,top[u]=t;
if(son[u])dfs2(son[u],u,t);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==p||j==son[u])continue;
dfs2(j,u,j);
}
}
//分块:
int bk[N],st[L],ed[L],bk_sum[L][N],bk_mx[L][N],len;
inline int query_bk(int l,int r,int tp,int opt){
int res=0;
for(int i=l;i<=r;i++){
if(!opt)res+=(c[q[i]]==tp)*v[q[i]];
else res=max(res,(c[q[i]]==tp)*v[q[i]]);
}
return res;
}//小块暴力求。
inline void query(int l,int r,int tp,int opt,int& res){
if(bk[l]==bk[r]){
if(!opt)res+=query_bk(l,r,tp,opt);
else res=max(res,query_bk(l,r,tp,opt));
}
else {
if(!opt)res+=query_bk(l,ed[bk[l]],tp,opt)+query_bk(st[bk[r]],r,tp,opt);
else res=max(res,max(query_bk(l,ed[bk[l]],tp,opt),query_bk(st[bk[r]],r,tp,opt)));
for(int i=bk[l]+1;i<=bk[r]-1;i++){
if(!opt)res+=bk_sum[i][tp];
else res=max(res,bk_mx[i][tp]);
}
}
}//大块直接统计
inline int query(int x,int y,int tp,int opt){
int res=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
int l=id[top[x]],r=id[x];
query(l,r,tp,opt,res);
x=fa[top[x]];
}
if(depth[x]>depth[y])swap(x,y);
int l=id[x],r=id[y];
query(l,r,tp,opt,res);
return res;
}//查询路径
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
memset(h,-1,sizeof h);
n=read(),m=read();
for(int i=1;i<=n;i++)v[i]=read(),c[i]=read();
for(int i=0;i<n-1;i++){
int a,b;
a=read(),b=read();
add(a,b),add(b,a);
}
dfs1(1,0),dfs2(1,0,1);
len=sqrt(1.6*n*log2(n))+1;
for(int i=1;i<=n;i++){
bk[i]=(i-1)/len;
if(!st[bk[i]])st[bk[i]]=i;
ed[bk[i]]=i;
bk_sum[bk[i]][c[q[i]]]+=v[q[i]];
bk_mx[bk[i]][c[q[i]]]=max(bk_mx[bk[i]][c[q[i]]],v[q[i]]);
}//分块预处理
for(int i=0;i<m;i++){
char opt[3];
read(opt);
if(!strcmp(opt,"CC")){
int x=read(),tp=read();
bk_sum[bk[id[x]]][c[x]]-=v[x];
bk_mx[bk[id[x]]][c[x]]=0,bk_mx[bk[id[x]]][tp]=0,swap(c[x],tp);
for(int j=st[bk[x]];j<=ed[bk[x]];j++){
if(c[q[j]]==tp)bk_mx[bk[id[x]]][tp]=max(bk_mx[bk[id[x]]][tp],v[q[j]]);
else if(c[q[j]]==c[x])bk_mx[bk[id[x]]][c[x]]=max(bk_mx[bk[id[x]]][c[x]],v[q[j]]);
}
bk_sum[bk[id[x]]][c[x]]+=v[x];
//暴力重构
}
else if(!strcmp(opt,"CW")){
int x=read(),val=read();
bk_sum[bk[id[x]]][c[x]]+=val-v[x],v[x]=val,bk_mx[bk[id[x]]][c[x]]=0;
for(int j=st[bk[x]];j<=ed[bk[x]];j++)
if(c[q[j]]==c[x])bk_mx[bk[id[x]]][c[x]]=max(bk_mx[bk[id[x]]][c[x]],v[q[j]]);
//暴力重构
}
else if(!strcmp(opt,"QS")){
int x=read(),y=read();
cout<<query(x,y,c[x],0)<<'\n';
}
else {
int x=read(),y=read();
cout<<query(x,y,c[x],1)<<'\n';
}
}
}