#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
using namespace std;
const int MX=4e5+9;
int n,in[MX],timer,org[MX],seg[MX*5],seg1[MX*5],ind[MX*5],indright[MX*5];
vector<int>v[MX];
void dfs(int x,int p){
in[x]=++timer;
org[timer]=x;
for(auto pp:v[x]){
if(pp==p)continue;
dfs(pp,x);
}
}
void build(int node,int l,int r){
if(l == r){
seg[node] = org[l];
ind[node] = indright[node] = l;
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
seg[node]=min(seg[node*2],seg[node*2+1]);
if(seg[node*2] < seg[node*2+1]) ind[node] = ind[node*2];
else ind[node] = ind[node*2+1];
if(seg[node*2] <= seg[node*2+1]) indright[node] = indright[node*2];
else indright[node] = indright[node*2+1];
}
pair<int,int> q(int node,int l,int r,int s,int e,bool ok){
if(l > e || r < s)return {MX,-1};
if(l >= s && r <= e){
if(ok == 0)return {seg[node],ind[node]};
return {seg[node],indright[node]};
}
int mid=(l+r)/2;
pair<int,int> p1=q(node*2,l,mid,s,e,ok);
pair<int,int> p2=q(node*2+1,mid+1,r,s,e,ok);
if(ok == 0){
if(p1.first < p2.first) return p1;
else return p2;
}
else{
if(p1.first <= p2.first) return p1;
else return p2;
}
}
void build1(int node,int l,int r){
if(l == r){
seg1[node] = org[l];
return;
}
int mid=(l+r)/2;
build1(node*2,l,mid);
build1(node*2+1,mid+1,r);
seg1[node]=max(seg1[node*2],seg1[node*2+1]);
}
int q1(int node,int l,int r,int s,int e){
if(l > e || r < s)return -1;
if(l >= s && r <= e)return seg1[node];
int mid=(l+r)/2;
return max(q1(node*2,l,mid,s,e),q1(node*2+1,mid+1,r,s,e));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R){
n=N;
for(int i=0;i<X.size();i++){
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
int root=0;
for(int i=0;i<n;i++){
if(v[i].size() == 1){
root = i;
}
}
dfs(root,-1);
build(1,1,n);
build1(1,1,n);
vector<int>res;
for(int i=0;i<S.size();i++){
int s=S[i],e=E[i];
if(s == e){
if(s >= L[i] && s <= R[i])res.push_back(1);
else res.push_back(0);
}
if(in[s] > in[e]){
int r=in[s],l=in[e];
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(q(1,1,n,mid,in[s],1).first >= L[i]){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans == -1){
res.push_back(0);
continue;
}
if(q1(1,1,n,in[e],ans) > R[i]){
res.push_back(0);
}
else res.push_back(1);
continue;
}
int l=in[s],r=in[e];
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(q(1,1,n,in[s],mid,0).first >= L[i]){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
if(ans == -1){
res.push_back(0);
continue;
}
if(q1(1,1,n,ans,in[e]) > R[i]){
res.push_back(0);
}
else res.push_back(1);
}
return res;
}
/*
10 9 7
3 9
9 1
1 0
0 4
4 2
2 5
5 6
6 8
8 10
3 8 1 8
4 9 3 10
3 5 3 8
2 8 1 10
8 4 7 9
4 6 3 5
6 4 3 5
*/
