#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200005];
int a[200005],pos[200005];
int last=0,cnt=0;
void dfs(int i,int p,int t){
pos[i]=cnt;
if(t==2) a[cnt++]=i;
last=i;
for(int j:adj[i]){
if(j==p) continue;
dfs(j,i,t);
}
}
int st1[200005][20],st2[200005][20];
void build(){
for(int i=0;i<cnt;i++){
st1[i][0]=st2[i][0]=a[i];
}
for(int j=1;j<20;j++){
for(int i=0;i<=cnt-(1<<j);i++){
st1[i][j]=min(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
st2[i][j]=max(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r,int t){
int k=log2(r-l+1);
//if(t==1) cout<<"QUERY MIN "<<l<<" "<<r<<" "<<min(st1[l][k],st1[r-(1<<k)+1][k])<<endl;
//else cout<<"QUERY MAX "<<l<<" "<<r<<" "<<max(st2[l][k],st2[r-(1<<k)+1][k])<<endl;
if(t==1) return min(st1[l][k],st1[r-(1<<k)+1][k]);
else return max(st2[l][k],st2[r-(1<<k)+1][k]);
}
int check(int s,int e,int m,int l,int r){
int q1=query(s,m,1),q2=query(m,r,2);
if(q1>=l&&q2<=r) return 0; //GOOD
if(q1>=l&&q2>r) return 1; //MOVE RIGHT
if(q1<l&&q2<=r) return 2; //MOVE LEFT
if(q1<l&&q2>r) return 3; //BAD
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
assert(X.size()==N-1);
for(int i=0;i<X.size();i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
dfs(0,-1,1);
dfs(last,-1,2);
vector<int>ans;
/*for(int i=0;i<N;i++){
cout<<a[i]<<" ";
}
cout<<endl;*/
build();
for(int i=0;i<S.size();i++){
int s=pos[S[i]],e=pos[E[i]],l=L[i],r=R[i];
if(s>e) swap(s,e);
int ll=s,rr=e;
while(ll<rr){
int mm=(ll+rr)/2;
int ch=check(s,e,mm,l,r);
if(ch==0){
ans.push_back(1);
goto hell;
}
else if(ch==3){
ans.push_back(0);
goto hell;
}
else if(ch==1) ll=mm+1;
else rr=mm-1;
if(ll>rr){
ans.push_back(0);
goto hell;
}
}
if(check(s,e,ll,l,r)){
ans.push_back(1);
}
else ans.push_back(0);
hell:;
}
return ans;
}
