#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
const int MAXN=2e5+10;
const int inf=1e8;
struct node{
int mx,mn;
node operator+(const node& o){
node c;
c.mx=max(o.mx,this->mx);
c.mn=min(o.mn,this->mn);
return c;
}
};
int n,pos[MAXN],rev[MAXN];
vector<int> g[MAXN];
node seg[4*MAXN];
void dfs(int x){
rev[pos[x]]=x;
for(auto u:g[x]){
if(pos[u]) continue;
pos[u]=pos[x]+1;
dfs(u);
}
}
void build(int ind,int l,int r){
if(l==r){
seg[ind].mx=seg[ind].mn=rev[l];
return;
}
int m=(l+r)>>1;
build(2*ind,l,m); build(2*ind+1,m+1,r);
seg[ind]=seg[2*ind]+seg[2*ind+1];
}
int walk(int ind,int l,int r,int a,int b,int val){
if(a>r || l>b || seg[ind].mn>=val) return inf;
if(l==r) return l;
int m=(l+r)>>1;
int x=walk(2*ind+1,m+1,r,a,b,val);
if(x!=inf) return x;
return walk(2*ind,l,m,a,b,val);
}
int w1(int ind,int l,int r,int a,int b,int val){
if(a>r || l>b || seg[ind].mx<=val) return -inf;
if(l==r) return l;
int m=(l+r)>>1;
int x=w1(2*ind,l,m,a,b,val);
if(x!=-inf) return x;
return w1(2*ind+1,m+1,r,a,b,val);
}
int w2(int ind,int l,int r,int a,int b,int val){
if(a>r || l>b || seg[ind].mn>=val) return -inf;
if(l==r) return l;
int m=(l+r)>>1;
int x=w2(2*ind,l,m,a,b,val);
if(x!=-inf) return x;
return w2(2*ind+1,m+1,r,a,b,val);
}
int w3(int ind,int l,int r,int a,int b,int val){
if(a>r || l>b || seg[ind].mx<=val) return inf;
if(l==r) return l;
int m=(l+r)>>1;
int x=w3(2*ind+1,m+1,r,a,b,val);
if(x!=inf) return x;
return w3(2*ind,l,m,a,b,val);
}
std::vector<int> check_validity(int N, 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=N;
fall(i,0,sz(X)-1){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
fall(i,0,n-1){
if(sz(g[i])==2) continue;
pos[i]=1;
dfs(i);
break;
}
build(1,0,n-1);
vector<int> ans(sz(R));
fall(i,0,sz(R)-1){
if(pos[E[i]]<pos[S[i]]){
int li=walk(1,0,n-1,pos[E[i]],pos[S[i]],L[i]);
int ri=w1(1,0,n-1,pos[E[i]],pos[S[i]],R[i]);
ans[i]=(ri>li+1);
}
else{
int li=w2(1,0,n-1,pos[S[i]],pos[E[i]],L[i]);
int ri=w3(1,0,n-1,pos[S[i]],pos[E[i]],R[i]);
ans[i]=(li>ri+1);
}
}
return ans;
}
