题面
给定一棵树，有点权
每次询问给出一些点对，求这些点对之间的路径的并集上不同权值的个数，以及这些权值的$mex$
思路
先考虑只有一对点对，只询问不同权值个数的问题：树上莫队模板题
然后加个$mex$：还是可以树上莫队
然后加入多组点对：这下不能莫队了
我们考虑另一种和莫队相似的算法：分块，在树上就是树分块
我们发现树分块要处理只有不同权值的问题的话，配合$bitset$食用会很好
预处理每个块顶到它的直系父亲块顶这条路径上的bitset
对于一个点对$(l,r)$，分开处理两条只有上下的链：$(l,lca)$和$(r,lca)$
链中间的部分跳块，两边的部分暴力跳
然后我们发现树分块+bitset可以处理多组点对的问题，因为bitset可以按位或起来
然后我们又发现bitset有一个叫find_first的东西，于是mex也解决了
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<bitset>
#include<queue>
#define last DEEP_DARK_FANTASY
#define ll long long
using namespace std;
inline int read(){
int re=0,flag=1;char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') flag=-1;
ch=getchar();
}
while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*flag;
}
int n,m,op;
int first[100010],cnte=-1;
struct edge{
int to,next;
}a[200010];int w[100010];
inline void add(int u,int v){
a[++cnte]=(edge){v,first[u]};first[u]=cnte;
a[++cnte]=(edge){u,first[v]};first[v]=cnte;
}
int dep[100010],siz[100010],son[100010],top[100010],fa[100010],dfn[100010],clk;
void dfs1(int u,int f){//树剖lca
int i,v;
fa[u]=f;
dep[u]=dep[f]+1;
siz[u]=1;son[u]=0;
for(i=first[u];~i;i=a[i].next){
v=a[i].to;if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int t){
int i,v;
top[u]=t;dfn[u]=++clk;
if(son[u]) dfs2(son[u],t);
for(i=first[u];~i;i=a[i].next){
v=a[i].to;if(v==son[u]||v==fa[u]) continue;
dfs2(v,v);
}
}
int lca(int l,int r){
while(top[l]!=top[r]){
if(dep[top[l]]>dep[top[r]]) swap(l,r);
r=fa[top[r]];
}
if(dep[l]>dep[r]) swap(l,r);
return l;
}
bitset<100010>tmp,st[150][150];
int id[100010],vis[100010],cntd,pos[100010],belong[100010],pre[100010],blk;
void getst(int u){
if(!u||vis[u]) return;
vis[u]=1;
id[u]=++cntd;
tmp.reset();
while(u){
tmp[w[u]]=1;
if(pre[u]==u){
st[cntd][belong[u]]=tmp;
}
u=fa[u];
}
}
void dfs(int u,int f){
int i,v;
for(i=first[u];~i;i=a[i].next){
v=a[i].to;if(v==f) continue;
if(belong[u]==belong[v]) pre[v]=pre[u];
else pre[v]=v;
dfs(v,u);
}
if(pre[u]==u) getst(fa[u]);
}
void build(){//树分块
int i,u,v;
for(i=1;i<=n;i++) pos[i]=i;
random_shuffle(pos+1,pos+n+1);//神秘的树分块技巧：随机块顶......
blk=min(n,150);
queue<int>q;
for(i=1;i<=blk;i++){
belong[pos[i]]=i;
q.push(pos[i]);
}
while(!q.empty()){
int u=q.front();q.pop();
for(i=first[u];~i;i=a[i].next){
v=a[i].to;if(belong[v]) continue;
q.push(v);belong[v]=belong[u];
}
}
pre[1]=1;
dfs(1,0);
}
inline void jump(int u,int v){
if(dep[u]<dep[v]) return;
while(u!=v){
tmp[w[u]]=1;
u=fa[u];
}
tmp[w[u]]=1;
}
inline void solve(int u,int t){
if(belong[u]==belong[t]){
jump(u,t);
return;
}
jump(u,pre[u]);
int v=fa[pre[u]],x=0;
while(dep[pre[v]]>=dep[t]){
x=belong[v];
v=fa[pre[v]];
}
if(x) tmp|=st[id[fa[pre[u]]]][x];
jump(v,t);
}
int main(){
memset(first,-1,sizeof(first));
n=read();m=read();op=read();
int i,t3,t1,t2,j,last=0;
for(i=1;i<=n;i++) w[i]=read();
for(i=1;i<n;i++){
t1=read();t2=read();
add(t1,t2);
}
dfs1(1,0);
dfs2(1,1);
build();
while(m--){
j=read();tmp.reset();
for(i=1;i<=j;i++){
t1=read();t2=read();
t1^=(last*op);
t2^=(last*op);
t3=lca(t1,t2);
solve(t1,t3);
solve(t2,t3);
}
t1=tmp.count();
tmp.flip();
t2=tmp._Find_first();
printf("%d %d
",t1,t2);
last=t1+t2;
}
}