#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pairll;
#define pb push_back
#define N 100007
#define fr first
#define sc second
ll n,a[8*N],b[8*N],d[2*N],k[2*N];
vector<ll>v[2*N];
vector<int>res;
void S1(ll x,ll y){
k[x]=k[y]+1;
d[k[x]]=x;
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=y)S1(v[x][i],x);
}
return ;
}
void BT(ll x,ll l,ll r){
if(l==r){
a[x]=d[l];
b[x]=d[l];
return ;
}
ll m1=(l+r)/2;
BT(x*2+1,l,m1);
BT(x*2+2,m1+1,r);
a[x]=min(a[x*2+1],a[x*2+2]);
b[x]=max(b[x*2+1],b[x*2+2]);
return ;
}
ll R1(ll x,ll l,ll r,ll tl,ll tr){
if(r<tl || tr<l)return n;
if(tl<=l && r<=tr)return a[x];
ll m1=(l+r)/2;
return min(R1(x*2+1,l,m1,tl,tr),R1(x*2+2,m1+1,r,tl,tr));
}
ll R2(ll x,ll l,ll r,ll tl,ll tr){
if(r<tl || tr<l)return 0;
if(tl<=l && r<=tr)return b[x];
ll m1=(l+r)/2;
return max(R2(x*2+1,l,m1,tl,tr),R2(x*2+2,m1+1,r,tl,tr));
}
std::vector<int> check_validity(int N1, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
n=N1;
for(int i=0;i<X.size();i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
for(int i=0;i<n;i++){
if(v[i].size()==1){
S1(i,i);
break;
}
}
for(int i=0;i<n;i++){
//cout<<k[i]<<" "<<i<<endl;
}
BT(0,1,n);
for(int i=0;i<S.size();i++){
ll x=S[i];
ll y=E[i];
if(k[x]<k[y]){
ll l=k[x];
ll r=k[y];
while(l<r){
ll m1=(l+r+1)/2;
if(R1(0,1,n,k[x],m1)>=L[i])l=m1;
else r=m1-1;
}
if(R1(0,1,n,k[x],l)>=L[i] && R2(0,1,n,l,k[y])<=R[i])res.pb(1);
else res.pb(0);
// cout<<l<<" "<<R1(0,1,n,k[x],l)<<" "<<R2(0,1,n,l,k[y])<<endl;
}else{
ll l=k[y];
ll r=k[x];
while(l<r){
ll m1=(l+r)/2;
if(R1(0,1,n,m1,k[x])>=L[i])r=m1;
else l=m1+1;
}
if(R1(0,1,n,l,k[x])>=L[i] && R2(0,1,n,k[y],l)<=R[i])res.pb(1);
else res.pb(0);
//cout<<l<<" "<<R1(0,1,n,l,k[x])<<" "<<R2(0,1,n,k[y],l)<<endl;
}
}
return res;
}
