#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N, Q, M;
vi S, E, L, R;
vvi adj;
vi depth;
struct fenwick
{
vi arr;
void init(int size)
{
arr.assign(size + 1, 0);
}
void add(int i, int v)
{
++i;
while (i < sz(arr))
arr[i] += v, i += i & (~i + 1);
}
int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); }
int query(int i)
{
++i;
int ans = 0;
while (i > 0)
ans += arr[i], i -= i & (~i + 1);
return ans;
}
};
void dfs(int v, int p)
{
depth[v] = depth[p] + 1;
for (int u : adj[v])
if (u != p)
dfs(u, v);
}
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)
{
N = _N, Q = sz(_S), M = sz(X);
S = _S, E = _E, L = _L, R = _R;
const int LOG = floor(log2(N));
adj.assign(N, vi());
for (int i = 0; i < M; ++i)
adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
int leaf = 0;
for (int i = 0; i < N; ++i)
if (sz(adj[i]) == 1)
leaf = i;
depth.assign(N, -1);
dfs(leaf, leaf);
vpii QR(Q), QL(Q);
for (int q = 0; q < Q; ++q)
QR[q] = {R[q], q}, QL[q] = {L[q], q};
sort(all(QR)), sort(all(QL));
reverse(all(QL));
fenwick fen;
fen.init(N);
auto computeBorder = [&](int v, pii &ret)
{
int l = v;
for (int j = LOG; j >= 0; --j)
if (l - (1 << j) >= 0 && fen.query(l - (1 << j), v) == v - (l - (1 << j)))
l -= 1 << j;
int r = v + 1;
for (int j = LOG; j >= 0; --j)
if (r + (1 << j) <= N && fen.query(v, r + (1 << j)) == (r + (1 << j) - v))
r += 1 << j;
ret = {l, r};
};
vpii SINT(Q), EINT(Q); // [l, r)
int idx = 0;
for (int i = 0; i < Q; ++i)
{
while (idx <= QR[i].first)
fen.add(depth[idx++], 1);
int q = QR[i].second;
computeBorder(depth[E[q]], EINT[q]);
}
idx = N - 1;
fen.init(N);
for (int i = 0; i < Q; ++i)
{
while (idx >= QL[i].first)
fen.add(depth[idx--], 1);
int q = QL[i].second;
computeBorder(depth[S[q]], SINT[q]);
}
std::vector<int> A(Q);
for (int q = 0; q < Q; ++q)
{
A[q] = max(EINT[q].first, SINT[q].first) < min(EINT[q].second, SINT[q].second);
}
return A;
}
