我都AFO了为什么还要我写题目

P多少多少默认洛谷

P3313 旅行

题意略，自己不会看吗

考虑对每个信仰开一个线段树，下标为dfs序，然后就是树剖板子

对于这种开一堆动态开点线段树的题目可以存每个线段树的根节点然后就只需要开一个结构体了

code:

#include<bits/stdc++.h>
#define lc t[now].ls
#define rc t[now].rs
using namespace std;
const int N=1e5+5;
int rt[N];

struct node{
	int ls,rs;
	int mx,sum;
}t[2000005];
int tot=100000;
int n,q,F[N],siz[N];
int son[N];
int W[N],C[N];
int id[N],top[N],dep[N];
vector<int> eg[N];

void dfs1(int now,int fa){
	dep[now]=dep[fa]+1;
	F[now]=fa;
	siz[now]=1;
	for(int i=0;i<eg[now].size();i++){
		int to=eg[now][i];
		if(to==fa) continue;
		dfs1(to,now);
		siz[now]+=siz[to];
		if(siz[to]>siz[son[now]]) son[now]=to;
	}
}
int cnt;
void dfs2(int now,int tp){
	id[now]=++cnt;
	top[now]=tp;
	if(son[now]){
		dfs2(son[now],tp);
	}
	for(int i=0;i<eg[now].size();i++){
		int to=eg[now][i];
		if(to==F[now] or to==son[now]) continue;
		dfs2(to,to);
	}
}

void pushup(int now){
	t[now].sum=t[lc].sum+t[rc].sum;
	t[now].mx=max(t[lc].mx,t[rc].mx);
}

int modi(int now,int l,int r,int X,int k){
	if(!now) now=++tot;
	if(l==r){
		t[now].sum=t[now].mx=k;
		return now;
	}
	int mid=(l+r)>>1;
	if(X<=mid) t[now].ls=(modi(t[now].ls,l,mid,X,k));
	else t[now].rs=(modi(t[now].rs,mid+1,r,X,k));
	pushup(now);
	return now;
}
int qsum(int now,int l,int r,int L,int R){
	if(!now or r<L or l>R) return 0;
	if(L<=l and r<=R){
		return t[now].sum; 
	}
	int mid=(l+r)>>1;
	return qsum(lc,l,mid,L,R)+qsum(rc,mid+1,r,L,R); 
}

int qmax(int now,int l,int r,int L,int R){
	if(!now or r<L or l>R) return 0;
	if(L<=l and r<=R){
		return t[now].mx; 
	}
	int mid=(l+r)>>1;
	return max(qmax(lc,l,mid,L,R),qmax(rc,mid+1,r,L,R)); 
}

int qlisum(int x,int y){
	int RT=rt[C[x]];
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans+=qsum(RT,1,n,id[top[x]],id[x]);
		x=F[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans+=qsum(RT,1,n,id[x],id[y]);
	return ans;
}

int qlimax(int x,int y){
	int RT=rt[C[x]];
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=max(ans,qmax(RT,1,n,id[top[x]],id[x]));
		x=F[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=max(ans,qmax(RT,1,n,id[x],id[y]));
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=tot;i++) rt[i]=i;
	for(int i=1;i<=n;i++){
		cin>>W[i]>>C[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		eg[u].push_back(v);
		eg[v].push_back(u);
	}
	dfs1(1,1);
	dfs2(1,1);
	for(int i=1;i<=n;i++){
		modi(rt[C[i]],1,n,id[i],W[i]);
	}
	for(int i=1;i<=q;i++){
		string opt;
		int x,y;
		cin>>opt>>x>>y;
		if(opt=="CC"){
			modi(rt[C[x]],1,n,id[x],0);
			modi(rt[(C[x]=y)],1,n,id[x],W[x]);
		}
		else if(opt=="CW"){
			W[x]=y;
			modi(rt[C[x]],1,n,id[x],W[x]);
		}
		else if(opt=="QS"){
			cout<<qlisum(x,y)<<"\n";
		}
		else cout<<qlimax(x,y)<<"\n";
	}
}

本人调了一个h，警戒各位搞清楚编号颜色之类的别写混了