#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n = 4e5 + 123;
int deg[n], used[n], pos[n], a[n];
int fl[2][n], fr[2][n];
vector <int> g[n];
void dfs(int v) {
used[v] = 1;
a[pos[v]] = v;
for (int to : g[v]) {
if (used[to]) continue;
pos[to] = pos[v] + 1;
dfs(to);
}
}
struct query {
int l, ind, t = 0;
bool operator < (const query & q) {
if (l == q.l) return t > q.t;
return l < q.l;
}
};
query q[n];
struct Node {
int l = 0, r = 0, mx, mn;
void clean() {
mn = n, mx = -n;
}
void merge(const Node & x, const Node & y) {
mx = max(x.mx, y.mx);
mn = min(x.mn, y.mn);
}
};
Node t[(1 << 19) + 1];
void build(int v, int l, int r) {
t[v].l = l, t[v].r = r;
if (l == r) {
t[v].clean();
return;
}
int m = l + r >> 1;
build(v << 1, l, m);
build(v << 1 | 1, m + 1, r);
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
Node tmp;
void get(int v, int l, int r) {
if (t[v].l > r || t[v].r < l) return;
if (t[v].l >= l && t[v].r <= r) {
tmp.merge(tmp, t[v]);
return;
}
get(v << 1, l, r), get(v << 1 | 1, l, r);
}
void upd(int v, int pos) {
if (t[v].l == t[v].r) {
t[v].mx = t[v].mn = t[v].l - 1;
return;
}
int m = t[v].l + t[v].r >> 1;
if (pos <= m) upd(v << 1, pos);
else upd(v << 1 | 1, pos);
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
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 M = X.size();
bool bamboo = (M == N - 1);
for (int i = 0; i < M; i++) {
deg[X[i]]++, deg[Y[i]]++;
g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
}
int root = -1;
for (int i = 0; i < N; i++) {
if (deg[i] > 2) bamboo = false;
if (deg[i] == 1) root = i;
}
int Q = S.size();
vector<int> A(Q);
if (bamboo) {
dfs(root);
for (int i = 0; i < Q; i++)
q[i].l = L[i] - 1, q[i].ind = i;
for (int i = 0; i < N; i++)
q[i + Q].l = a[i], q[i + Q].ind = i, q[i + Q].t = 1;
sort(q, q + N + Q);
build(1, 1, N);
for (int i = 0; i < N + Q; i++) {
if (q[i].t == 0) {
int l = pos[S[q[i].ind]], r = pos[E[q[i].ind]];
if (l > r) swap(l, r);
tmp.clean(), get(1, l + 1, r + 1);
fl[0][q[i].ind] = tmp.mn - 1;
fl[1][q[i].ind] = tmp.mx + 1;
q[i].l = -(R[q[i].ind] + 1);
} else {
upd(1, q[i].ind + 1);
q[i].l = -q[i].l;
}
}
sort(q, q + N + Q);
build(1, 1, N);
for (int i = 0; i < N + Q; i++) {
if (q[i].t == 0) {
int l = pos[S[q[i].ind]], r = pos[E[q[i].ind]];
if (l > r) swap(l, r);
tmp.clean(), get(1, l + 1, r + 1);
fr[0][q[i].ind] = tmp.mn - 1;
fr[1][q[i].ind] = tmp.mx + 1;
} else upd(1, q[i].ind + 1);
}
for (int i = 0; i < Q; i++) {
int l = pos[S[i]], r = pos[E[i]];
if (l > r) {
A[i] = (fr[0][i] >= fl[1][i]);
} else {
A[i] = (fl[0][i] >= fr[1][i]);
}
}
} else assert(false);
return A;
}
/*
7 6 2
2 3
3 0
0 1
6 2
4 5
4 1
1 6 2 3
6 1 2 3
*/
