ggsg.cpp

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define vi vector<int>
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()

struct Z{
	vi p,x,l,r,h,u,g,kz,kk,ans;
	vector<vi> z;
	int w,m,q,s,e,d,t;

	void build(vi&a,vi&b){
		p=vi(w),l=vi(w),r=vi(w),z=vector<vi>(w),h=vi(w);
		rep(i,1,w)z[a[i]].push_back(i);
		vi vis(w),stk={0};p[0]=b[0];
		while(sz(stk)){
			int v=stk.back();
			if(!vis[v]){
				l[v]=t++;x.pb(p[v]);vis[v]=1;
				for(int j=sz(z[v])-1;~j;--j)p[z[v][j]]=p[v]^b[z[v][j]],stk.pb(z[v][j]);
			}else r[v]=t-1,stk.pop_back();
		}
	}

	void inc(int i){int y=g[i];if(!u[y]++)kk[y/d]++;}
	void dec(int i){int y=g[i];if(!--u[y])kk[y/d]--;}
	int grab(int c){
		rep(bi,0,(m+d-1)/d){
			if(c>kk[bi])c-=kk[bi];
			else{
				int st=bi*d,en=min(st+d,m);
				rep(i,st,en)if(u[i]&&!--c)return kz[i];
			}
		}
		return -1;
	}

	vi solve(vi&a,vi&b,vector<vi>&qq){
		w=sz(a),t=0,build(a,b);
		kz=x,sort(all(kz)),kz.erase(unique(all(kz)),kz.end()),m=sz(kz);
		g=vi(w);rep(i,0,w)g[i]=lower_bound(all(kz),x[i])-kz.begin();
		d=sqrt(m)+1,u=vi(m),kk=vi((m+d-1)/d);
		q=sz(qq),s=sqrt(w)+1;
		struct qr{int i,j,k,id,b;};
		vector<qr> vq(q);
		rep(i,0,q)vq[i]={l[qq[i][0]],r[qq[i][0]],qq[i][1],i,l[qq[i][0]]/s};
		sort(all(vq),[](qr&a,qr&b){return a.b!=b.b?a.b<b.b:((a.b&1)?a.j<b.j:a.j>b.j);});
		e=0,d=-1,ans=vi(q);
		for(auto &z:vq){
			while(e>z.i)inc(--e);
			while(d<z.j)inc(++d);
			while(e<z.i)dec(e++);
			while(d>z.j)dec(d--);
			ans[z.id]=grab(z.k);
		}
		return ans;
	}
};

class Solution{
public:
	vi (vi&a,vi&b,vector<vi>&qq){
		Z zz; return zz.solve(a,b,qq);
	}
};