#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n;
const int N=200090;
int idx[N],vis[N],a[N],treemn[N*4],treemx[N*4];
vector<int>v[N];
void go (int x,int y)
{
idx[x]=y;
a[y]=x;
vis[x]=1;
for(auto it:v[x])
{
if(vis[it])
continue;
go(it,y+1);
}
}
int get1 (int ind,int st,int end,int l,int r,int x)
{
if(r<l)
return 0;
if(l>end||r<st)
return (end-st+1);
int m=(st+end )/2;
int re=0;
if(l<=st&&end<=r)
{
if(st==end&&a[st]<=x)
return 1;
else if(st==end)
return 0;
if(treemx[ind]<=x)
return (end-st+1);
if(treemx[ind*2+1]<=x)
{
re=get1(ind*2+2,m+1,end,l,r,x);
re+=m+1-st;
return re;
}
re=get1(ind*2+1,st,m,l,r,x);
return re;
}
re=get1(ind*2+1,st,m,l,r,x);
if(re==m+1-st)
{
re+=get1(ind*2+2,m+1,end,l,r,x);
return re;
}
return re;
}
int get (int ind,int st,int end,int l,int r,int x)
{
if(r<l)
return 0;
if(l>end||r<st)
return (end-st+1);
int m=(st+end )/2;
int re=0;
if(l<=st&&end<=r)
{
if(st==end&&a[st]>=x)
return 1;
else if(st==end)
return 0;
if(treemn[ind]>=x)
return (end-st+1);
if(treemn[ind*2+1]>=x)
{
re=get(ind*2+2,m+1,end,l,r,x);
re+=m+1-st;
return re;
}
re=get(ind*2+1,st,m,l,r,x);
return re;
}
re=get(ind*2+1,st,m,l,r,x);
if(re==m+1-st)
{
re+=get(ind*2+2,m+1,end,l,r,x);
return re;
}
return re;
}
void build(int ind,int st,int end)
{
if(st==end)
{
treemx[ind]=a[st];
treemn[ind]=a[st];
return;
}
int m=(st+end)/2;
build(ind*2+1,st,m);
build(ind*2+2,m+1,end);
treemn[ind]=min(treemn[ind*2+1],treemn[ind*2+2]);
treemx[ind]=max(treemx[ind*2+1],treemx[ind*2+2]);
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
memset(a,0,sizeof a);
memset(treemn,0,sizeof treemn);
memset(treemx,0,sizeof treemx);
memset(idx,0,sizeof idx);
for(int i=0; i<n+3; i++)
a[i]=n+1;
for(int i=0; i<n+3; i++)
v[i].clear();
n=N;
int m=X.size();
for(int i=0; i<m; i++)
{
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
int st=0;
for(int i=0; i<n; i++)
{
if(v[i].size()==1)
{
st=i;
break;
}
}
vector<int>ans;
ans.clear();
go(st,1);
build(0,1,n);
int q=S.size();
for(int i=0; i<q; i++)
{
int s=S[i],e=E[i],l=L[i],r=R[i];
if(s<l||e>r)
{
ans.pb(0);
continue;
}
if(idx[s]>idx[e])
{
int x=get1(0,1,n,idx[e],n,r);
if(x>=idx[s])
{
ans.pb(1);
continue;
}
if(a[x]<l)
{
ans.pb(0);
continue;
}
x=get(0,1,n,x,n,l);
if(x>=idx[s])
ans.pb(1);
else
ans.pb(0);
continue;
}
int x=get(0,1,n,idx[s],n,l);
if(x>=idx[e])
{
ans.pb(1);
continue;
}
if(a[x]>r)
{
ans.pb(0);
continue;
}
x=get1(0,1,n,x,n,r);
if(x>=idx[e])
ans.pb(1);
else
ans.pb(0);
}
return ans;
}
