#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> st1;
void upd1(int v, int tl, int tr, int pos, int val){
if(tl==tr)st1[v]=val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)upd1(v*2,tl,tm,pos,val);
else upd1(v*2+1,tm+1,tr,pos,val);
st1[v]=min(st1[v*2],st1[v*2+1]);
}
}
int wk1(int v, int tl, int tr, int val){
if(tl==tr)return tl;
int tm=(tl+tr)/2;
if(st1[v]>=val)return tr+1;
if(st1[v*2]<val)return wk1(v*2,tl,tm,val);
return wk1(v*2+1,tm+1,tr,val);
}
vector<int> st2;
void upd2(int v, int tl, int tr, int pos, int val){
if(tl==tr)st2[v]=val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)upd2(v*2,tl,tm,pos,val);
else upd2(v*2+1,tm+1,tr,pos,val);
st2[v]=min(st2[v*2],st2[v*2+1]);
}
}
int wk2(int v, int tl, int tr, int val){
if(tl==tr)return tl;
int tm=(tl+tr)/2;
if(st2[v]>=val)return tl-1;
if(st2[v*2+1]<val)return wk2(v*2+1,tm+1,tr,val);
return wk2(v*2,tl,tm,val);
}
vector<int> st3;
void upd3(int v, int tl, int tr, int pos, int val){
if(tl==tr)st3[v]=val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)upd3(v*2,tl,tm,pos,val);
else upd3(v*2+1,tm+1,tr,pos,val);
st3[v]=max(st3[v*2],st3[v*2+1]);
}
}
int wk3(int v, int tl, int tr, int val){
if(tl==tr)return tl;
int tm=(tl+tr)/2;
if(st3[v]<=val)return tr+1;
if(st3[v*2]>val)return wk3(v*2,tl,tm,val);
return wk3(v*2+1,tm+1,tr,val);
}
vector<int> st4;
void upd4(int v, int tl, int tr, int pos, int val){
if(tl==tr)st4[v]=val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)upd4(v*2,tl,tm,pos,val);
else upd4(v*2+1,tm+1,tr,pos,val);
st4[v]=max(st4[v*2],st4[v*2+1]);
}
}
int wk4(int v, int tl, int tr, int val){
if(tl==tr)return tl;
int tm=(tl+tr)/2;
if(st4[v]<=val)return tl-1;
if(st4[v*2+1]>val)return wk4(v*2+1,tm+1,tr,val);
return wk4(v*2,tl,tm,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) {
int q = S.size();
int m=X.size();
int n=N;
vector<int> a(q,0);
vector<int> w(n);
int st=-1;
vector<vector<int>> adj(n);
for(int i=0;i<n-1;i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i=0;i<n;i++){
if(adj[i].size()==1){
st=i;
break;
}
}
vector<int> rev(n);
vector<int> norm(n);
norm[0]=st;
rev[st]=0;
int pre=st;
int cr=adj[st][0];
while(true){
rev[cr]=rev[pre]+1;
norm[rev[cr]]=cr;
int prepre=pre;
pre=cr;
if(adj[cr].size()==1)break;
if(adj[cr][0]==prepre)cr=adj[cr][1];
else cr=adj[cr][0];
}
st1.clear();
st2.clear();
st3.clear();
st4.clear();
st1.resize(4*n,100000000);
st2.resize(4*n,100000000);
st3.resize(4*n,-1);
st4.resize(4*n,-1);
vector<pair<int,int>> qu1;
vector<pair<int,int>> qu2;
vector<pair<int,int>> qu3;
vector<pair<int,int>> qu4;
for(int i=0;i<q;i++){
if(rev[S[i]]<rev[E[i]]){
qu1.push_back({rev[S[i]],i});
qu4.push_back({rev[E[i]],i});
}
else{
qu2.push_back({rev[S[i]],i});
qu3.push_back({rev[E[i]],i});
}
}
vector<int> l1(q);
vector<int> r1(q);
sort(qu1.begin(),qu1.end());
sort(qu2.begin(),qu2.end());
int cj=n-1;
for(int i=qu1.size()-1;i>=0;i--){
while(cj>=qu1[i].first){
upd1(1,0,n-1,cj,norm[cj]);
cj--;
}
l1[qu1[i].second]=wk1(1,0,n-1,L[qu1[i].second]);
}
cj=0;
for(int i=0;i<qu2.size();i++){
while(cj<=qu2[i].first){
upd2(1,0,n-1,cj,norm[cj]);
cj++;
}
l1[qu2[i].second]=wk2(1,0,n-1,L[qu2[i].second]);
}
sort(qu3.begin(),qu3.end());
sort(qu4.begin(),qu4.end());
cj=n-1;
for(int i=qu3.size()-1;i>=0;i--){
while(cj>=qu3[i].first){
upd3(1,0,n-1,cj,norm[cj]);
cj--;
}
r1[qu3[i].second]=wk3(1,0,n-1,R[qu3[i].second]);
}
cj=0;
for(int i=0;i<qu4.size();i++){
while(cj<=qu4[i].first){
upd4(1,0,n-1,cj,norm[cj]);
cj++;
}
r1[qu4[i].second]=wk4(1,0,n-1,R[qu4[i].second]);
}
for(int i=0;i<q;i++){
if(rev[S[i]]<rev[E[i]]){
if(l1[i]>r1[i]+1)a[i]=1;
}
else{
if(l1[i]+1<r1[i])a[i]=1;
}
}
return a;
}
