#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int MXN = 200005, MXK = 20;
vector<int> adj[MXN];
vector<int> ord;
void dfs(int node, int par = -1) {
ord.push_back(node);
for (auto x: adj[node]) {
if (x == par) continue;
dfs(x, node);
}
}
int stmax[MXN][MXK];
int stmin[MXN][MXK];
int pos[MXN];
int qmax(int l, int r) {
int k = (r - l + 1);
int t = 31 - __builtin_clz(k);
return max(stmax[l][t], stmax[r-(1<<t)+1][t]);
}
int qmin(int l, int r) {
int k = (r - l + 1);
int t = 31 - __builtin_clz(k);
return min(stmin[l][t], stmin[r-(1<<t)+1][t]);
}
pair<int, int> around(int center, int minokay, int maxokay) {
int low = 0;
int high = center + 1;
while (low + 1 < high) {
int mid = (low + high) / 2;
if ((qmin(mid, center) < minokay) || (qmax(mid, center) > maxokay)) {
low = mid;
}
else {
high = mid;
}
}
int L = low;
if ((qmin(low, center) < minokay) || (qmax(low, center) > maxokay)) L++;
low = center;
high = n;
while (low + 1 < high) {
int mid = (low + high) / 2;
if ((qmin(center, mid) < minokay) || (qmax(center, mid) > maxokay)) {
high = mid;
}
else {
low = mid;
}
}
int R = low;
if ((qmin(center, low) < minokay) || (qmax(center, low) > maxokay)) R--;
return {L, R};
}
bool itr(pair<int, int> a, pair<int, int> b) {
if (a > b) swap(a, b);
return (b.first >= a.first && b.first <= a.second);
}
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();
vector<int> A;
n = N;
int M = X.size();
for (int i=0; i<M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int starter = -1;
for (int i=0; i<N; i++) {
if (adj[i].size() == 1) starter = i;
}
dfs(starter);
for (int i=0; i<MXN; i++) {
for (int j=0; j<MXK; j++) {
stmax[i][j] = INT_MAX;
stmin[i][j] = INT_MIN;
}
}
for (int i=0; i<N; i++) {
pos[ord[i]] = i;
stmax[i][0] = ord[i];
stmin[i][0] = ord[i];
}
for (int j=1; j<MXK; j++) {
int L = 1 << (j - 1);
for (int i=0; i<N; i++) {
if (i + L < N) {
stmax[i][j] = max(stmax[i][j-1], stmax[i+L][j-1]);
stmin[i][j] = min(stmin[i][j-1], stmin[i+L][j-1]);
}
}
}
for (int i=0; i<Q; i++) {
int s = S[i], e = E[i], l = L[i], r = R[i];
int spos = pos[s];
int epos = pos[e];
if (ord[spos] < l || ord[epos] > r) {
A.push_back(0);
continue;
}
pair<int, int> srange = around(spos, l, N-1);
pair<int, int> erange = around(epos, 0, r);
A.push_back(itr(srange, erange));
}
return A;
}
