有毒
第一开始一直RE，我就把dfs改成了bfs
结果一直TLE，自己造的数据要跑8s
因为 lxl 等人讲随机 $\sqrt{n}$ 个点作为关键点就可以了
但是我把随机改成深度有关就AC了，而且那组数据跑了200ms
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define For(i,a,b) for(int i=(a),i##_end=(b);i<i##_end;++i)
#define per(i,a,b) for(int i=(b),i##_st=(a);i>=i##_st;--i)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define dbg(x) cerr<<#x" = "<<x<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Es(x,i) for(Edge*i=G[x];i;i=i->nxt)
typedef long long ll;
typedef pair<int,int> pii;
const int inf=~0u>>1,MOD=1e9+7;
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=((TT=but)+fread(but,1,1<<15,stdin)),TT==mo))?-1:*TT++)
inline int rd() {
int x,c,f=1;while(!isdigit(c=getchar()))f=c!='-';x=c-'0';
while(isdigit(c=getchar()))x=x*10+c-'0';return f?x:-x;
}
#define Q 64
const int N=100011,MX=30000/Q+2,Modx=131;
typedef unsigned long long ui;
#define lb _lb_
int fx[1<<16],fy[Modx];
inline int pcal(){
For(i,1,1<<16)fx[i]=fx[i^(i&-i)]+1;
ui t=1;
fy[1]=0;
For(i,1,Q)t<<=1,fy[t%Modx]=i;
}
inline int cal1(unsigned int i){
//cout<<i<<" f "<<fx[i&((1<<16)-1)]+fx[i>>16]<<endl;
return fx[i&((1<<16)-1)]+fx[i>>16];
} inline int cal(ui i){
unsigned int a=i>>32,b=i&(~0ull);
return cal1(a)+cal1(b);
}
inline int lb(ui i){
return fy[i%Modx];
}
struct bs{
ui w[MX];
bs (int _t=1){if(!_t)memset(w,0,sizeof w);}
void Ci(){memset(w,0,sizeof w);}
//inline uint&operator&(int i){return w[i];}
void operator|=(const bs&b){
For(i,0,MX)this->w[i]|=b.w[i];
} bs operator|(const bs&b)const{
static bs c;
c.Ci();
For(i,0,MX)c.w[i]=w[i]|b.w[i];
return c;
}
inline void in(int i){
int j=i>>6;i&=(63);
w[j]|=(1ull<<i);
}
inline pii query(){
static const ui I=~0ull;
//cerr<<I<<endl;
//int t=clock();
int a=0,b;
For(i,0,MX)if(w[i]!=I){
ui t=w[i];int p=0;
t=~t;
t=t&-t;
//while(t&1)t>>=1,++p;
b=(i<<6)+lb(t);break;
}
For(i,0,MX)if(w[i]){
a+=cal(w[i]);
//cout<<i<<" "<<w[i]<<endl;
}
//dbg(clock()-t);
return mp(a,b);
}
#undef Q
} b[(int)(1.8*N+1000)],*it=b;
struct Edge{int v;Edge*nxt;}pl[N<<1],*cur=pl,*G[N];
inline void ins(int u,int v){*cur=(Edge){v,G[u]},G[u]=cur++;}
int n,rt,a[N],m,bel[N],fa[N];
int L[N],tot;
int Top[N],dep[N],son[N],sz[N],q[N];
inline void dfs(int S){
int h,t=1;q[h=0]=S;
while(h<t){
int x=q[h++];
dep[x]=dep[fa[x]]+1,sz[x]=1;
Es(x,i)if(i->v!=fa[x]){
fa[q[t++]=i->v]=x;
}
}
per(o,0,t-1){
int x=q[o];
Es(x,i)if(i->v!=fa[x]){
sz[x]+=sz[i->v];
if(sz[i->v]>sz[son[x]])son[x]=i->v;
}
}
For(o,0,t){
int x=q[o];
Top[x]=(son[fa[x]]==x)?Top[fa[x]]:x;
}
}
inline void dfs2(int S){
For(o,0,n){
int x=q[o];
L[x]=tot; if(!bel[x])bel[x]=bel[fa[x]];
else if(x!=rt){
it->in(a[x]);
int t=fa[x],y=bel[t],lst=-1;
while(bel[t]==y){
it->in(a[t]);
lst=t,t=fa[t];
}
++tot,++it;
while(t>0){
*it=b[L[lst]]|*(it-1);
++it,++tot;
if((lst=bel[t])==-1)break;
else t=fa[lst];
}
//R[x]=tot;
} } }
inline void Init(){
rt=rand()%n+1;
dfs(rt);
rep(i,1,n){
if(dep[i]%200==0)bel[i]=i;
}
bel[rt]=-1;
dfs2(rt);
}
bs A;
inline int lca(int x,int y){
while(Top[x]!=Top[y]){
if(dep[Top[x]]<dep[Top[y]])swap(x,y);
x=fa[Top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline void query(int x,int y){
//int t=clock();
int l=lca(x,y);
{
//dbg(x),dbg(rt),dbg(l);
while(bel[x]!=x&&x!=l)A.in(a[x]),x=fa[x];//dbg(x);
if(bel[x]==x){
int e=L[x],f=x,g=bel[fa[x]];
while(g>0&&dep[g]>=dep[l])++e,f=g,g=bel[fa[g]];
if(e>L[x])A|=b[e-1];//cout<<"fff\n";;
while(f!=l)A.in(a[f]),f=fa[f];
}
}
//cerr<<"OK1"<<endl;
swap(x,y);
{
while(bel[x]!=x&&x!=l)A.in(a[x]),x=fa[x];
if(bel[x]==x){
int e=L[x],f=x,g=bel[fa[x]];
while(g>0&&dep[g]>=dep[l])++e,f=g,g=bel[fa[g]];
if(e>L[x])A|=b[e-1];//cout<<"fff\n";;
while(f!=l)A.in(a[f]),f=fa[f];
}
}
A.in(a[l]);
}
int main(){
#ifdef flukehn
freopen("test.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
srand((unsigned long long)(new char));
pcal();
n=rd();int q=rd(),f=rd(),lst=0;
rep(i,1,n)a[i]=rd();
For(i,1,n){
int x=rd(),y=rd();
ins(x,y),ins(y,x);
}
Init();
// dbg(clock());
// if(n>=90000)return 0;
while(q--){
//cerr<<q<<endl;
//int t=clock();
A.Ci();
int a=rd();
while(a--){int x=rd()^(f?lst:0),y=rd()^(f?lst:0);query(x,y);}
//cerr<<q<<endl;
pii tmp=A.query();
lst=tmp.fi+tmp.se;
printf("%d %d\n",tmp.fi,tmp.se);
//dbg(clock()-t);
//cerr<<q<<endl;
} // cerr<<clock()<<endl;
}