树剖31pts求调教

#include<bits/stdc++.h>
#define int long long
#define double long double
#define INF INT_MAX
using namespace std;
const int maxn=1e5+5;
int n,q,cnt;
int a[maxn];
int f[maxn],deap[maxn],siz[maxn],son[maxn];
int id[maxn],p[maxn],top[maxn],dfn[maxn];
vector<int> g[maxn];
set<int> ans[maxn];
void dfs1(int dq,int fa,int sum){
	f[dq]=fa,deap[dq]=sum,siz[dq]=1;
	int maxson=-1;
	for(int i=0;i<g[dq].size();i++){
		if(g[dq][i]==fa) continue;
		dfs1(g[dq][i],dq,sum+1);
		siz[dq]+=siz[g[dq][i]];
		if(maxson==-1 || siz[g[dq][i]]>siz[maxson]) maxson=g[dq][i],son[dq]=g[dq][i];
	}
	return;
}
void dfs2(int dq,int fa){
	id[dq]=++cnt,dfn[cnt]=dq,p[cnt]=a[dq],top[dq]=fa;
	if(!son[dq]) return;
	dfs2(son[dq],fa);
	for(int i=0;i<g[dq].size();i++){
		if(g[dq][i]==f[dq] || g[dq][i]==son[dq]) continue;
		dfs2(g[dq][i],g[dq][i]);
	}
	return;
}
struct Tree{
	int val,add;
	#define sum(x) t[x].val
	#define add(x) t[x].add
}t[maxn*4];
void up_date(int dq){sum(dq)=sum(dq*2)+sum(dq*2+1);}
void build(int dq,int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	build(dq*2,l,mid);
	build(dq*2+1,mid+1,r);
	up_date(dq);
}
void spread(int dq,int l,int r){
	if(add(dq)){
		int mid=(l+r)/2;
		sum(dq*2)=(mid-l+1)*add(dq);
		sum(dq*2+1)=(r-mid)*add(dq);
		add(dq*2)+=add(dq);
		add(dq*2+1)+=add(dq);
		add(dq)=0;
	}
}
void change(int dq,int ll,int rr,int l,int r,int d){
	if(l<=ll && rr<=r){
		sum(dq)+=d*(rr-ll+1);
		add(dq)+=d;
		return;
	}
	spread(dq,ll,rr);
	int mid=(ll+rr)/2;
	if(l<=mid) change(dq*2,ll,mid,l,r,d);
	if(r>mid) change(dq*2+1,mid+1,rr,l,r,d);
	up_date(dq);
}
int ask(int dq,int ll,int rr,int l,int r){
	if(l<=ll && rr<=r) return sum(dq);
	spread(dq,ll,rr);
	int res=0,mid=(ll+rr)/2;
	if(l<=mid) res+=ask(dq*2,ll,mid,l,r);
	if(r>mid) res+=ask(dq*2+1,mid+1,rr,l,r);
	return res;
}
void changee(int x,int y,int d){
	while(top[x]!=top[y]){
		if(deap[top[x]]<deap[top[y]]){
			change(1,1,n,id[top[y]],id[y],d);
			y=f[top[y]];
		}
		else{
			change(1,1,n,id[top[x]],id[x],d);
			x=f[top[x]];
		}
	}
	if(deap[x]<deap[y]) change(1,1,n,id[x]+1,id[y],d);
	else change(1,1,n,id[y]+1,id[x],d);
}
int askk(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(deap[top[x]]<deap[top[y]]){
			res+=ask(1,1,n,id[top[y]],id[y]);
			y=f[top[y]];
		}
		else{
			res+=ask(1,1,n,id[top[x]],id[x]);
			x=f[top[x]];
		}
	}
	if(deap[x]<deap[y]) res+=ask(1,1,n,id[x]+1,id[y]);
	else res+=ask(1,1,n,id[y]+1,id[x]);
	return res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	while(q--){
		char op;
		int x,y;
		cin>>op>>x>>y;
		if(op=='P') changee(x,y,1);
		if(op=='Q') cout<<askk(x,y)<<endl;
	}
	return 0;
}