#include <bits/stdc++.h>
#include "werewolf.h"
//#include "grader.cpp"
using namespace std;
const int MX=2e5+9;
int n,in[MX],timer,org[MX],seg[MX*5],seg1[MX*5],ind[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] = 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];
}
pair<int,int> q(int node,int l,int r,int s,int e){
if(l > e || r < s)return {MX,-1};
if(l >= s && r <= e)return {seg[node],ind[node]};
int mid=(l+r)/2;
pair<int,int> p1=q(node*2,l,mid,s,e);
pair<int,int> p2=q(node*2+1,mid+1,r,s,e);
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(in[s] > in[e])swap(s,e);
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).first >= L[i]){
ans=q(1,1,n,in[s],mid).second;
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;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
