#include <bits/stdc++.h>
#include "werewolf.h"
#define pb push_back
#define INF 1000000009
using namespace std;
list<int> adj[200005];
int arr[200005];
int st[200005*4][2];
int n;
void carr(int i, int node, int anc){
arr[i] = node;
for (list<int>::iterator it = adj[node].begin(); it != adj[node].end(); ++it){
if (*it == anc) continue;
carr(i+1, *it, node);
}
}
void stc(int node, int l, int r, int mode){
if (l == r) st[node][mode] = arr[l];
else {
int mid = (l+r)/2;
stc(node*2, l, mid, mode);
stc(node*2+1, mid+1, r, mode);
if (mode == 0){
st[node][mode] = min(st[node*2][mode], st[node*2+1][mode]);
} else {
st[node][mode] = max(st[node*2][mode], st[node*2+1][mode]);
}
}
}
int stq(int node, int l, int r, int mode, int sl, int sr){
if (sl <= l && r <= sr){
return st[node][mode];
} else if (r < sl || l < sr){
if (mode == 0) return INF;
else return -1;
} else {
int mid = (l+r)/2;
if (mode == 0){
return min(stq(node*2, l, mid, mode, sl, sr), stq(node*2+1, mid+1, r, mode, sl, sr));
} else {
return max(stq(node*2, l, mid, mode, sl, sr), stq(node*2+1, mid+1, r, mode, sl, sr));
}
}
}
pair<int, int> check(int s, int m, int t, int l, int r){
pair<int, int> ans = make_pair(0, 0);
int minn = stq(1, 0, n-1, 0, s, m);
if (minn >= l) ans.first = 1;
int maxx = stq(1, 0, n-1, 1, m, t);
if (maxx <= r) ans.second = 1;
return ans;
}
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 < n; i++){
adj[X[i]].pb(Y[i]);
}
int nodes = -1;
for (int i = 0; i < n; i++){
if (adj[i].size() == 1){
nodes = i;
break;
}
}
carr(0, nodes, -1);
stc(1, 0, n-1, 0);
stc(1, 0, n-1, 1);
int Q = S.size();
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
int l = min(S[i], E[i]);
int r = max(S[i], E[i]);
int s = l;
int t = r;
while (l < r){
int mid = (l+r)/2;
pair<int, int> ans = check(s, mid, t, L[i], R[i]);
if (ans.first == 0 && ans.second == 0){
break;
} else if (ans.first == 0 && ans.second == 1){
r = mid-1;
} else if (ans.first == 1 && ans.second == 0){
l = mid+1;
} else {
break;
}
}
pair<int, int> ans = check(s, l, t, L[i], R[i]);
A[i] = (ans.first == 1 && ans.second == 1);
}
return A;
}
