#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector< vector< int > > Graph;
int LAST = -1;
int curr = 1;
vector< int > v;
void dfs(int node, int last){
LAST = node;
v[curr++] = node;
for(int a : Graph[node]){
if(a == last) continue;
dfs(a, node);
}
}
////////////////////////////////////////////////
struct node{
node* l, *r;
int mini, maxi;
void update(){
mini = min(l->mini, r->mini);
maxi = max(l->maxi, r->maxi);
}
};
void Build(node* root, int left, int right){
if(left == right){
root->mini = root->maxi = v[left];
return;
}
int mid = (left+right)/2;
root->l = new node{NULL,NULL,0,0};
root->r = new node{NULL,NULL,0,0};
Build(root->l, left, mid);
Build(root->r, mid+1, right);
root->update();
}
pair<int, int> Query(node* root, int left, int right, int qLeft, int qRight){
if(left > qRight || right < qLeft) return {INT_MAX, INT_MIN};
if(left >= qLeft && right <= qRight){
return {root->mini, root->maxi};
}
int mid = (left+right)/2;
pair<int, int> p = Query(root->l, left, mid, qLeft, qRight);
pair<int, int> q = Query(root->r, mid+1, right, qLeft, qRight);
return {min(p.first, q.first), max(p.second, q.second)};
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size();
int M = X.size();
Graph.resize(N);
v.resize(N+1);
for(int i = 0; i < M; i++){
Graph[X[i]].push_back(Y[i]);
Graph[Y[i]].push_back(X[i]);
}
dfs(0,-1);
curr = 1;
dfs(LAST,-1);
vector< int > pos(N);
for(int i = 1; i <= N; i++){
pos[v[i]] = i;
}
node *root = new node{NULL,NULL,0,0};
Build(root, 1, N);
vector< int > ans(Q);
for(int i = 0; i < Q; i++){
if(S[i] < L[i] || E[i] > R[i]){
ans[i] = 0;
continue;
}
int A = pos[S[i]];
int B = pos[E[i]];
if(A < B){
int left = A;
int right = B;
//cout << "First" << endl;
while(left < right){
// cout << left << ' ' << right << endl;
int mid = (left+right+1)/2;
pair<int, int> p = Query(root, 1, N, A, mid);
if(p.first < L[i]){
right = mid-1;
}else{
left = mid;
}
}
pair<int, int> p = Query(root, 1, N, left, B);
if(p.second <= R[i]){
ans[i] = 1;
}else{
ans[i] = 0;
}
}else{
int left = B;
int right = A;
//cout << "SECOND " << endl;
while(left < right){
//cout << left << ' ' << right << endl;
//if(left == 3 && right == 4) return ans;
int mid = (left+right+1)/2;
pair<int, int> p = Query(root, 1, N, B, mid);
if(p.second > R[i]){
right = mid-1;
}else{
left = mid;
}
}
pair<int, int> p = Query(root, 1, N, left, A);
if(p.first >= L[i]){
ans[i] = 1;
}else{
ans[i] = 0;
}
}
}
return ans;
}
