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;
}