Steven_Meng's Blog

传送门

考虑每个宗教建立一棵线段树，但是空间会炸，考虑动态开点。

时间复杂度$O(n \log n)$，空间复杂度$O(n \log n)$

#include <bits/stdc++.h>
#define MAXN 100005
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<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void swap(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}
vector<int>G[MAXN];
int value[MAXN],size[MAXN],fa[MAXN],dep[MAXN],top[MAXN],id[MAXN],Bigson[MAXN];
int root[MAXN],cnt;
void dfs(int u,int father){
	fa[u]=father;
	size[u]=1;
	Bigson[u]=0;
	dep[u]=dep[father]+1;
	for (register int i=0;i<G[u].size();++i){
		if (G[u][i]!=father){
			dfs(G[u][i],u);
			size[u]+=size[G[u][i]];
			if (Bigson[u]==0||size[G[u][i]]>size[Bigson[u]]){
				Bigson[u]=G[u][i];
			}
		}
	}
}
void dfs2(int u,int Top){
	top[u]=Top;
	id[u]=++cnt;
	if (!Bigson[u]){
		return ;
	}
	dfs2(Bigson[u],Top);
	for (register int i=0;i<G[u].size();++i){
		if (G[u][i]!=fa[u]&&G[u][i]!=Bigson[u]){
			dfs2(G[u][i],G[u][i]);
		}
	}
}
struct SegmentTree{
    struct node{
        int l,r;
        int maxn,sum;
    }tree[MAXN<<5];
    #define lc tree[i].l
    #define rc tree[i].r
    int tot_node;
	SegmentTree(){
		tot_node=0;
	}
    void pushup(int i){
        tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn);
        tree[i].sum=tree[lc].sum+tree[rc].sum;
    }
    void update(int &i,int L,int R,int pos,int val){
        if (!i) i=++tot_node;
        if (L==R){
            tree[i].maxn=tree[i].sum=val;
            return ;
        }
        int mid=(L+R)>>1;
        if (pos<=mid) update(lc,L,mid,pos,val);
        else update(rc,mid+1,R,pos,val);
        pushup(i);
    }
    int query_max(int i,int qL,int qR,int L,int R){
		if (qL<=L&&R<=qR){
			return tree[i].maxn;
		}
		int mid=(L+R)>>1;
		int ans=-0x7fffffff;
		if (qL<=mid) ans=max(ans,query_max(lc,qL,qR,L,mid));
		if (mid<qR) ans=max(ans,query_max(rc,qL,qR,mid+1,R));
		return ans;
    }
    int query_sum(int i,int qL,int qR,int L,int R){
		if (qL<=L&&R<=qR){
			return tree[i].sum;
		}
		int mid=(L+R)>>1,ans=0;
		if (qL<=mid) ans+=query_sum(lc,qL,qR,L,mid);
		if (mid<qR) ans+=query_sum(rc,qL,qR,mid+1,R);
		return ans;
	}
	#undef lc
	#undef rc
}Seg;
int w[MAXN],c[MAXN],n;
inline int query_ans(int u,int v,int type){//type==0 sum type==1 max
	int color=c[u];
	int sum=0,maxval=-0x7fffffff;
	while (top[u]!=top[v]){
		if (dep[top[u]]<dep[top[v]]){
			swap(u,v);
		}
		if (type==0){
			sum+=Seg.query_sum(root[color],id[top[u]],id[u],1,cnt);
		}
		else {
			maxval=max(maxval,Seg.query_max(root[color],id[top[u]],id[u],1,cnt));
		}
		u=fa[top[u]];
	}
	if (id[u]>id[v]){
		swap(u,v);
	}
	if (type==0){
		sum+=Seg.query_sum(root[color],id[u],id[v],1,cnt);
		return sum;
	}
	else {
		maxval=max(maxval,Seg.query_max(root[color],id[u],id[v],1,cnt));
		return maxval;
	}
}
int main(){
	int q;
	n=read(),q=read();
	for (register int i=1;i<=n;++i){
		w[i]=read(),c[i]=read();
	}
	for (register int i=1;i<n;++i){
		int u,v;
		u=read(),v=read();
		G[u].push_back(v),G[v].push_back(u);
	}
	dfs(1,1),dfs2(1,1);
	for (register int i=1;i<=n;++i){
		Seg.update(root[c[i]],1,n,id[i],w[i]);
	}
	char opr[10];
	while (q--){
		scanf("%s",opr);
		if (opr[0]=='C'){
			if (opr[1]=='C'){
				int u,color;
				u=read(),color=read();
				Seg.update(root[c[u]],1,n,id[u],0);
				Seg.update(root[c[u]=color],1,n,id[u],w[u]);
			}
			else{
				int u,weight;
				u=read(),weight=read();
				Seg.update(root[c[u]],1,n,id[u],w[u]=weight);
			}
		}
		else if (opr[0]=='Q'){
			printf("%d\n",query_ans(read(),read(),opr[1]=='M'));
		}
	}
}