rt
菜菜求助
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
int n,m,q;
int a[MAXN];
struct bian {
int x,y,ls;
}b[MAXN];
int t[MAXN],cnt;
int c[MAXN],nn;
int fd[MAXN];
void jb(int x,int y) {
cnt ++;
b[cnt].x = x;
b[cnt].y = y;
b[cnt].ls = t[x];
t[x] = cnt;
}
map<int,int>lsp;
int ctn = 0;
void rd() {
cin >> n >> q;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
if(!lsp.count(a[i])) {
ctn ++;
lsp[a[i]] = ctn;
a[i] = ctn;
} else {
a[i] = lsp[a[i]];
}
}
for(int i = 1; i < n; i ++) {
int x,y;
cin >> x >> y;
jb(x,y);
jb(y,x);
}
}
bitset<40005>p[100][100];
int S;
bitset<40005>r;
int bl[MAXN],fa[MAXN],h[MAXN];
int cr[MAXN];
void get(int x,int fr,int ls) {
cr[a[x]] ++;
if(cr[a[x]] == 1) r[a[x]] = 1;
if(fd[x]) {
p[fr][fd[x]] = r;
}
for(int i = t[x]; i != 0;i = b[i].ls) {
int y = b[i].y;
if(y != ls) get(y,fr,x);
}
cr[a[x]] --;
if(cr[a[x]] == 0) r[a[x]] = 0;
}
int fuck[MAXN];
void dfs(int x) {
if(fd[x]) {
bl[x] = fd[x];
fuck[fd[x]] = bl[fa[x]];
} else bl[x] = bl[fa[x]];
h[x] = h[fa[x]] + 1;
for(int i = t[x]; i; i = b[i].ls) {
int y = b[i].y;
if(y != fa[x]) {
fa[y] = x;
dfs(y);
}
}
}
int lastans;
void no_head_dp(int x,int y)
{
while(h[x] > h[y]) {
r[ a[x] ] = 1;
x = fa[x];
}
while(h[y] > h[x]) {
r[ a[y] ] = 1;
y = fa[y];
}
while(x != y) {
r[a[x]] = 1; r[a[y]] = 1;
x = fa[x];
y = fa[y];
}
r[a[x]] = 1;
}
int kd[MAXN];
int mh;
signed main()
{
rd();
S = sqrt(n)*2;
fd[1] = 1;
nn ++; c[1] = 1;
for(int i = 2; i <= n; i ++) {
int o = rand()%S;
if(o == 0 && nn < 99) {
nn ++;
fd[i] = nn;
kd[fd[i]] = i;
c[nn] = i;
}
}
for(int i = 1; i <= nn; i ++) {
r.reset();
memset(cr,0,sizeof(cr));
get(c[i],i,0);
}
dfs(1);
for(int i = 1; i <= n; i ++)
mh = max(h[i],mh);
for(int i = 1; i <= q; i ++) {
int x,y;
cin >> x >> y;
x ^= lastans;
if(x > n) continue;
r.reset();
if(bl[x] == bl[y]) {
no_head_dp(x,y);
} else {
if(h[x] < h[y]) swap(x,y);
int t = bl[x],fl = 0,g = t;
while(t) {
t = fuck[t];
if(t == bl[y]) {
fl = 1; break;
}
g = t;
}
if(!fl) {
r = p[bl[x]][bl[y]];
while(!fd[x]) {
r[ a[x] ] = 1;
x = fa[x];
}
while(!fd[y]) {
r[ a[y] ] = 1;
y = fa[y];
}
} else {
r = p[bl[x]][g];
while(!fd[x]) {
r[ a[x] ] = 1;
x = fa[x];
}
no_head_dp(kd[g],y);
}
}
lastans = r.count();
cout<<lastans<<"\n";
}
return 0;
}