#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
vector<int> mn, mx;
void build(int tl, int tr, int i, vector<int> &V) {
if (tl == tr) {
mn[i] = mx[i] = V[tl];
return ;
}
int tm = (tl + tr) / 2;
build(tl, tm, i * 2, V);
build(tm + 1, tr, i * 2 + 1, V);
mn[i] = min(mn[i * 2], mn[i * 2 + 1]);
mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
}
int query(int t, int ql, int qr, int tl, int tr, int i) {
if (ql > qr) {
if (t) return -INF;
else return INF;
}
if (ql == tl && qr == tr) {
if (t) return mx[i];
else return mn[i];
}
int tm = (tl + tr) / 2;
if (t) return max(query(t, ql, min(qr, tm), tl, tm, i * 2), query(t, max(ql, tm + 1), qr, tm + 1, tr, i * 2 + 1));
return min(query(t, ql, min(qr, tm), tl, tm, i * 2), query(t, max(ql, tm + 1), qr, tm + 1, tr, i * 2 + 1));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
// furthest T from S such that [S, T] has no i < L
// after transforming at T, is there a city i in [T, E] where i > R
int Q = S.size();
vector<int> A(Q);
vector<int> V(N), P(N, -1); // V[i] = population, P[pop] = i
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]);
}
int root; for(int i = 0; i < N; i++) if (adj[i].size() == 1) root = i;
int cur = root, cnt = 0;
while(true) {
P[cur] = cnt;
V[cnt++] = cur;
if (P[adj[cur][0]] == -1) cur = adj[cur][0];
else if (P[adj[cur][1]] == -1) cur = adj[cur][1];
else break;
}
mn.resize(N*4), mx.resize(N*4);
build(0, N-1, 1, V);
for(int q = 0; q < Q; q++) {
int s = S[q], e = E[q];
if (e < s) {
int l = e, r = s+1;
while(l < r) {
int m = (l + r) / 2;
if (query(0, m, s, 0, N-1, 1) >= L[q]) r = m;
else l = m + 1;
}
A[q] = query(1, e, l, 0, N-1, 1) <= R[q];
} else {
int l = s, r = e+1;
while(l < r - 1) {
int m = (l + r) / 2;
if (query(0, s, m, 0, N-1, 1) >= L[q]) l = m;
else r = m;
}
A[q] = query(1, l, e, 0, N-1, 1) <= R[q];
}
}
return A;
}
