题目
题目描述
奇怪的大学有一座奇怪的花园，花园由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运算符
输出格式
对于每个询问操作，给出答案
样例
样例输入
1 | 5 8 |
样例输出
1 | 1 |
数据范围与提示
样例解释
这是加密前的操作：1
2
3
4
5
6
7
8Q 2 5 10
C 3 20
Q 2 5 20
C 4 20
Q 3 5 30
C 5 20
Q 2 5 20
Q 1 3 10
数据规模与约定
对于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$就可以了
附上代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using namespace std;
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;
}
}
}