#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> V;
vector<vector<int>> adj;
vector<vector<int>> T;
int n;
void dfs(int cur,int prev){
V.push_back(cur);
for(auto x:adj[cur]){
if(x!=prev){
dfs(x,cur);
}
}
}
void build(int i,int l,int r){
if(l==r){
T[i]={V[l]};
return;
}
int m=(l+r)/2;
build(2*i+1,l,m);
build(2*i+2,m+1,r);
merge(T[2*i+1].begin(),T[2*i+1].end(),T[2*i+2].begin(),T[2*i+2].end(),back_inserter(T[i]));
}
int query(int i,int tl,int tr,int l,int r,int x){
if(tl>=l && tr<=r){
int ans=upper_bound(T[i].begin(),T[i].end(),x)-T[i].begin();
return ans;
}
if(tl>r || tr<l){
return 0;
}
int m=(tl+tr)/2;
return query(2*i+1,tl,m,l,r,x)+query(2*i+2,m+1,tr,l,r,x);
}
int qu(int l,int r,int x){
return query(0,0,n-1,l,r,x);
}
vector<int> check_validity(int N,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();
unordered_map<int,int> M,M1;
adj.resize(N);
n=N;
for(int i=0;i<X.size();i++){
M[X[i]]++;
M[Y[i]]++;
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int start;
for(auto x:M){
if(x.second==1){
start=x.first;
break;
}
}
dfs(0,-1);
T.resize(4*N);
vector<int> ans;
build(0,0,n-1);
for(int i=0;i<V.size();i++){
M1[V[i]]=i;
}
for(int i=0;i<S.size();i++){
int a=M1[S[i]];
int b=M1[E[i]];
if(a>b){
swap(a,b);
}
int c=qu(a,b,L[i]-1);
int d=qu(a,b,R[i]);
if(c>1){
ans.push_back(0);
continue;
}else if(c<1){
if(d>0){
ans.push_back(1);
}else{
ans.push_back(0);
}
}else{
ans.push_back(1);
continue;
}
}
return ans;
}
