#include "werewolf.h"
#include <queue>
#include <vector>
#include <stdio.h>
using namespace std;
queue < pair < int , int > > all;
vector < int > Next[200005];
bool have[5][200005];
int con[200005]={0};
int what[200005];
int cha[200005],now=1;
struct A
{
int l,r;
int nxl,nxr;
int big,small;
}Node[2000005];
void F(int here,int fa,int deg)
{
what[deg]=here;
cha[here]=deg;
for(auto i:Next[here]) if(i!=fa) F(i,here,deg+1);
}
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].nxl=now++;
Node[here].nxr=now++;
if(l==r)
{
Node[here].big=what[l];
Node[here].small=what[l];
return ;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
}
int Find1(int l,int r,int here)
{
if(Node[here].l==l&&Node[here].r==r) return Node[here].small;
if(r<=(Node[here].l+Node[here].r)/2) return Find1(l,r,Node[here].nxl);
if(l>(Node[here].l+Node[here].r)/2) return Find1(l,r,Node[here].nxr);
else return min(Find1(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find1((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
int Find2(int l,int r,int here)
{
if(Node[here].l==l&&Node[here].r==r) return Node[here].big;
if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxl);
if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,Node[here].nxr);
else return max(Find2(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find2((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R)
{
int Q = S.size(),M=X.size(),i,j,ok,a,b,l,r;
vector<int> A(Q);
vector<int> B(Q);
for(i=0;i<M;i++)
{
Next[X[i]].push_back(Y[i]);
Next[Y[i]].push_back(X[i]);
con[X[i]]++;
con[Y[i]]++;
}
if(N<=3000)
{
for(i=0;i<Q;i++)
{
//if(S[i]!=83069||S[i])
for(j=0;j<N;j++) have[0][j]=have[1][j]=0;
ok=0;
all.push(make_pair(S[i],0));
while(!all.empty())
{
a=all.front().first;
b=all.front().second;
all.pop();
if(a==E[i]&&b==1)
{
ok=1;
break;
}
if(have[b][a]) continue;
if(b==0&&a<L[i]) continue;
if(b==1&&a>R[i]) continue;
have[b][a]=1;
if(b==0&&a>=L[i]&&a<=R[i]) all.push(make_pair(a,1));
for(auto i:Next[a]) all.push(make_pair(i,b));
}
while(!all.empty()) all.pop();
A[i]=ok;
B[i]=ok;
//printf("%d ",ok);
//printf("\n");
}
//printf("\n");
}
else
{
for(i=0;i<N;i++)
{
if(con[i]==1)
{
all.push(make_pair(i,-1));
for(j=0;j<N;j++)
{
what[j]=all.front().first;
cha[all.front().first]=j;
for(auto k:Next[all.front().first]) if(k!=all.front().second) all.push(make_pair(k,all.front().first));
all.pop();
}
break;
}
}
build(0,N-1,0);
for(i=0;i<Q;i++)
{
a=cha[S[i]];
b=cha[E[i]];
//printf("%d %d\n",a,b);
if(what[a]<L[i])
{
A[i]=0;
continue;
}
if(what[b]>R[i])
{
A[i]=0;
continue;
}
if(a<b)
{
l=a;
r=b+1;
while((r-l)>1)
{
if(Find1(a,(l+r)/2,0)>=L[i]) l=(l+r)/2;
else r=(l+r)/2;
}
if(what[l]<L[i]) l--;
if(Find2(l,b,0)<=R[i]) A[i]=1;
else A[i]=0;
}
else
{
l=b;
r=a;
while((r-l)>1)
{
if(Find1((l+r)/2,a,0)>=L[i]) r=(l+r)/2;
else l=(l+r)/2;
}
if(what[l]<L[i]) l++;
if(Find2(b,l,0)<=R[i]) A[i]=1;
else A[i]=0;
}
}
}
/*for(i=0;i<Q;i++)
{
if(A[i]!=B[i])
{
printf("%d %d %d %d %d %d %d\n",i,A[i],B[i],cha[S[i]],cha[E[i]],S[i],E[i]);
printf("%d %d\n",L[i],R[i]);
for(j=cha[S[i]];j<=cha[E[i]];j++) printf("%d ",what[j]);
}
}*/
return A;
}
