CF1083C Max Mex

题面传送门
我们考虑一条链的mex值为\(k\)的条件。显然需要满足\(0\)~\(k-1\)均出现在这条链上。
但是这不充分。不过因为题目中要求的是最大值，所以一定最大值所在链满足这个条件就合法。所以我们可以认为这是充分条件。
首先我们如何判断一个值\(k\)是否合法？
很简单，看看有没有一条链能覆盖\(0\)~\(k-1\)的所有点即可，这个可以用线段树加上st表的\(O(1)\)LCA维护。
然后在线段树上二分，时间复杂度大常数\(O((n+q)logn)\)
code:

#include
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define RI re int
#define ll long long
#define db double
#define lb long db
#define N 200000
#define M 500000
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*x+(y))
#define R(n) (rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound 
using namespace std;
int n,m,P[N+5],Id[N+5],Dfn[N+5<<1],x,y,op,lg[N+5<<1],Bg[N+5],H,T[N+5<<1][20],d[N+5];
struct yyy{int to,z;};struct ljb{int head,h[N+5];yyy f[N+5];I void add(int x,int y){f[++head]=(yyy){y,h[x]};h[x]=head;}}s;
I void dfs(int x,int La){Dfn[Bg[x]=++H]=x;d[x]=d[La]+1;yyy tmp;for(RI i=s.h[x];i;i=tmp.z) tmp=s.f[i],dfs(tmp.to,x),Dfn[++H]=x;}
I int LCA(int x,int y){x=Bg[x];y=Bg[y];x>y&&(swap(x,y),0);int D=lg[y-x+1];return d[T[x][D]]>1;BD(l,m,ls);BD(m+1,r,rs);Up(now);}
	I void Ins(int x,int l=0,int r=n-1,int now=1){if(l==r) {F[now]=(Ques){Id[x],Id[x],1};return;}int m=l+r>>1;x<=m?Ins(x,l,m,ls):Ins(x,m+1,r,rs);Up(now);}
	I int Find(Ques x,int l=0,int r=n-1,int now=1){if(l==r) return x=Merge(x,F[now]),~x.Fl?l+1:l;int m=l+r>>1;return ~Merge(x,F[ls]).Fl?Find(Merge(x,F[ls]),m+1,r,rs):Find(x,l,m,ls);}
	#undef ls
	#undef rs
}
int main(){
	freopen("1.in","r",stdin);
	RI i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&P[i]),Id[P[i]]=i;for(i=2;i<=n;i++)scanf("%d",&x),s.add(x,i);dfs(1,0);for(i=2;i<=H;i++) lg[i]=lg[i/2]+1;
	for(i=H;i;i--) for(T[i][0]=Dfn[i],j=1;i+(1<