可持续化线段树好题

[题目链接] (https://ac.nowcoder.com/acm/contest/1083/F)
题解：这题如果不连边的话，就只需要用普通线段树来维护就行了，注意递推关系，如ABCBA可以由AB和CBA组成，但是你同时还要递推AB，所以需要递推所有的关系。那么这题加边了，就用可持续化线段树来维护，如果不知道可持续化线段树，建议先学习。那么这道题我们只需要找到查询的两个节点的公共祖先，然后分别查属于他们的线段树中的区间子串中ABCBA的个数了。

#include<bits/stdc++.h>
#define m (l+r)/2
using namespace std;
const int maxn = 3e4+10,mod = 10007;
char s[maxn];
struct node {
    int cat, A, AB, ABC, ABCB, B, BC, BCB, BCBA, C, CB, CBA, BA;
    node operator+(const node &t) const {
        node tmp;
        tmp.cat = (cat + t.cat + A * t.BCBA + AB * t.CBA + ABC * t.BA + ABCB * t.A) % mod;
        tmp.A = (A + t.A) % mod;
        tmp.AB = (AB + t.AB + A * t.B) % mod;
        tmp.ABC = (ABC + t.ABC + A * t.BC + AB * t.C) % mod;
        tmp.ABCB = (ABCB + t.ABCB + A * t.BCB + AB * t.CB + ABC * t.B) % mod;
        tmp.B = (B + t.B) % mod;
        tmp.BC = (BC + t.BC + B * t.C) % mod;
        tmp.BCB = (BCB + t.BCB + B * t.CB + BC * t.B) % mod;
        tmp.BCBA = (BCBA + t.BCBA + B * t.CBA + BC * t.BA + BCB * t.A) % mod;
        tmp.C = (C + t.C) % mod;
        tmp.CB = (CB + t.CB + C * t.B) % mod;
        tmp.CBA = (CBA + t.CBA + C * t.BA + CB * t.A) % mod;
        tmp.BA = (BA + t.BA + B * t.A) % mod;
        return tmp;
    }
} tr[maxn * 20];
int cnt=0 ,ls[maxn*20] , rs[maxn*20] , rt[maxn] ;
int n,q;
vector<int>G[maxn];
void up(int &o,int pre,int l,int r,int k,char c)
{
	o = ++cnt;
	ls[o] = ls[pre];
	rs[o] = rs[pre];
	if(l==r)
	{
		if(c=='A') tr[o].A = 1;
		else if(c=='B') tr[o].B = 1;
		else if(c=='C') tr[o].C = 1;
		return ;
	}
	if(k>m) up(rs[o],rs[pre],m+1,r,k,c);
	else up(ls[o],ls[pre],l,m,k,c);
	tr[o] = tr[ls[o]] + tr[rs[o]];
}
node qu(int o,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r)
	return tr[o];
	if(ql>m) return qu(rs[o],m+1,r,ql,qr);
	else if(qr<=m) return qu(ls[o],l,m,ql,qr);
	else return qu(ls[o],l,m,ql,qr) + qu(rs[o],m+1,r,ql,qr);
}
int f[maxn][20] ,dep[maxn];
void dfs(int u,int fa)
{
	f[u][0] =fa;
	dep[u] =dep[fa] + 1;
	for(int i=1;i<18;i++)
	f[u][i] = f[f[u][i-1]][i-1];
	up(rt[u],rt[fa],1,n,dep[u],s[u]);
	for(auto v: G[u])
	if(v!=fa)dfs(v,u);
}
int LCA(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=17;~i;i--)
	if(dep[f[u][i]]>=dep[v])
	u = f[u][i];
	if(u==v) return u;
	for(int i=17;~i;i--)
		if(f[u][i]!=f[v][i])
		u = f[u][i] , v= f[v][i];
	return f[u][0];
}
int main()
{
	int u,v;
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	for(int i=1;i<n;i++)
	{
	scanf("%d%d",&u,&v);
	G[u].push_back(v);
	G[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&u,&v);
		int ans = 0;
		int lca = LCA(u,v);
		if(u==lca||v==lca)
		{
			node t ;
			if(u!=lca) t = qu(rt[u],1,n,dep[lca],dep[u]);
			else t = qu(rt[v],1,n,dep[lca],dep[v]);
			ans = t.cat % mod; 
		}
		else  {
			node t1,t2;
			t1 = qu(rt[u],1,n,dep[lca],dep[u]);
			t2 = qu(rt[v],1,n,dep[lca]+1,dep[v]);
			ans = (t1.cat + t2.cat + t1.A*t2.BCBA+t1.BA*t2.CBA+t1.CBA*t2.BA+t1.BCBA*t2.A)%mod;
		}
		printf("%d\n",ans);
	}
}

提醒一下：在由t1，t2计算ans 时，t1需要是逆序，相信你学过主席树后，应该很容易理解。