题目

题目描述

奇怪的大学有一座奇怪的花园，花园由N座温室组成，温室依次标号为$1,2,\cdots \cdots ,N$，温室之间由$N-1$条双向道路连接
每一座温室都种植这一种花，随着季节的变换，温室里的花的种类也在不断发生着变化
ShenX平时非常喜欢在花园中漫步，他想知道从温室$x$走到温室$y$的路径中（包括两个端点），第$t$种花出现的次数

输入格式

第一行为两个整数$N,Q$，分别表示温室的数目和操作的数目
第二行有N个整数$T_1,T_2,\cdots \cdots,T_n$，其中$T_i$表示温室$i$中的花的种类
接下来$N-1$行，每个两个整数$x,y$，表示温室$x$和温室$y$之间有一条双向道路
接下来$Q$行，表示$Q$个操作，分别为以下两种形式之一：

C x t 表示在温室$x$中的花的种类变为$t$
Q x y t 表示询问温室$x$走到温室$y$的路径中（包括两个端点），第t种花出现的次数

为了体现在线操作，输入数据中的每个操作的参数都进行了加密。记最后一次询问的答案为$anslast$（一开始没有进行过询问时设$anslast$为$0$），读入中的$x,y,t$均需要异或上$anslast$以得到真实值，在c/c++中异或为^运算符，在Pascal中为xor运算符

输出格式

对于每个询问操作，给出答案

样例

样例输入

5 8
10 20 30 40 50 
1 2
1 3
3 4
3 5
Q 2 5 10
C 2 21
Q 3 4 21
C 6 22
Q 1 7 28
C 5 20
Q 2 5 20
Q 2 0 9

样例输出

数据范围与提示

样例解释

这是加密前的操作：

数据规模与约定

对于30%的数据，有$N\leqslant 1000，Q\leqslant 2000$
对于50%的数据，有$N\leqslant 10000，Q\leqslant 20000$
对于100%的数据，有$1\leqslant N<100000，1\leqslant Q\leqslant 200000,0\leqslant Ti<2^{31}$

题解

因为这是一棵树，所以我们可以假设根是$1$号节点
我们设$S(x)$表示$1$号节点到$x$号节点的路径上第$t$种花的数量，$v(x)$表示$x$号节点上是第几种花
那么，$x$号节点到$y$号节点的路径上第$t$种花的数量为$S(x)+S(y)-S(lca)+[v(lca)==t]$
所以我们就只需要求出$S(x)$就可以了
咋求呢？线段树！
所以我们可以对每一种花开一棵线段树，由于内存的限制，我们需要使用动态开点
问题是如何修改呢？
我们可以对于每一个节点，记录下这个节点的DFS序，就可以进行修改了！
修改时只需要把这个点DFS序的起始到结束中间的所有数都$+1$就可以了
附上代码：

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define l(x) t[x].l
#define r(x) t[x].r
#define a(x) t[x].add
#define v(x) t[x].val
struct Segment_Tree
{
    int l,r,add,val;
}t[10000010];
map<int,int> val;
int n,q,ans,sum,size,T[100010],root[300010];
int tot,top,head[100010],to[200010],nxt[200010],dep[100010],fa[100010][20],dfn[200010],b[100010],e[100010];
void add(int u,int v)
{
    nxt[++tot]=head[u],head[u]=tot,to[tot]=v;
}
void dfs(int x)
{
    dfn[++top]=x;
    for(int i=1;i<=16;i++)
        if((1<<i)<=dep[x]) fa[x][i]=fa[fa[x][i-1]][i-1];
        else break;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa[x][0]) fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);
    dfn[++top]=x;
}
int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    int temp=dep[u]-dep[v];
    for(int i=0;i<=16;i++) if(temp&(1<<i)) u=fa[u][i];
    for(int i=16;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return u==v?u:fa[u][0];
}
void spread(int p,int l,int r)
{
    if(!a(p)||l==r) return;
    int temp=a(p);
    if(!l(p)) l(p)=++size;
    if(!r(p)) r(p)=++size;
    a(p)=0,v(l(p))+=temp,a(l(p))+=temp,v(r(p))+=temp,a(r(p))+=temp;
}
void change(int &p,int l,int r,int x,int y,int d)
{
    if(!p) p=++size;
    spread(p,l,r);
    if(x==l&&y==r){v(p)+=d,a(p)+=d;return;}
    int mid=(l+r)>>1;
    if(x<=mid) change(l(p),l,mid,x,min(y,mid),d);
    if(y>mid) change(r(p),mid+1,r,max(x,mid+1),y,d);
}
int ask(int p,int l,int r,int x)
{
    if(!p) return 0;
    spread(p,l,r);
    if(l==r) return v(p);
    int mid=(l+r)>>1;
    if(x<=mid) return ask(l(p),l,mid,x);
    else return ask(r(p),mid+1,r,x);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&T[i]);
        if(!val[T[i]]) val[T[i]]=++sum;
        T[i]=val[T[i]];
    }
    for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs(1);
    for(int i=1;i<=top;i++)
        if(!b[dfn[i]]) b[dfn[i]]=i;
        else e[dfn[i]]=i;
    for(int i=1;i<=n;i++) change(root[T[i]],1,top,b[i],e[i],1);
    for(int i=1,x,y,z;i<=q;i++){
        char op[3];
        scanf("%s %d%d",op,&x,&y),x^=ans,y^=ans;
        if(op[0]=='Q'){
            scanf("%d",&z),z^=ans;
            int LCA=lca(x,y);
            if(!val[z]){ans=0,printf("0\n");continue;}
            z=val[z],ans=ask(root[z],1,top,b[x])+ask(root[z],1,top,b[y])-2*ask(root[z],1,top,b[LCA]);
            if(T[LCA]==z) ans++;
            printf("%d\n",ans);
        }
        if(op[0]=='C'){
            if(!val[y]) val[y]=++sum;
            y=val[y],change(root[T[x]],1,top,b[x],e[x],-1),change(root[y],1,top,b[x],e[x],1),T[x]=y;
        }
    }
}