#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct Seg {
struct Node {
int mini, maxi;
static Node join(Node const& a, Node const& b) {
return Node{min(a.mini, b.mini), max(a.maxi, b.maxi)};
}
};
int n;
vector<Node> tree;
vector<int> const& v;
Seg(vi const& v) : n(v.size()), tree(n*4), v(v) {
build(0, 0, n-1);
};
void build(int no, int l, int r) {
if (l == r) {
tree[no] = Node{v[l], v[l]};
return;
}
int m = (l+r)/2;
build(no*2+1, l, m);
build(no*2+2, m+1, r);
tree[no] = Node::join(tree[no*2+1], tree[no*2+2]);
}
Node get(int no, int l, int r, int a, int b) {
if (a <= l and r <= b) return tree[no];
int m = (l+r)/2;
if (b <= m) return get(no*2+1, l, m, a, b);
if (a > m) return get(no*2+2, m+1, r, a, b);
return Node::join(get(no*2+1, l, m, a, b),
get(no*2+2, m+1, r, a, b));
}
};
int const maxn = 202020;
vector<int> vt[maxn];
vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
int q = S.size();
for (int i = 0; i < n; i++) {
vt[X[i]].push_back(Y[i]);
vt[Y[i]].push_back(X[i]);
}
int beg = 0;
for (int i = 0; i < n; i++) if (vt[i].size() == 1) beg = i;
vector<int> v(n);
v[0] = beg;
vector<int> pos(n, -1);
pos[beg] = 0;
for (int i = 1; i < n; i++) {
int last = v[i-1];
for (int u : vt[last]) {
if (pos[u] != -1) continue;
v[i] = u;
pos[u] = i;
}
}
vector<int> res(q);
Seg sg(v);
for (int i = 0; i < q; i++) {
int source = S[i], dest = E[i];
if (pos[source] > pos[dest]) swap(source, dest);
int l = L[i], r = R[i];
int x = pos[source] - 1, y = pos[dest];
while (y-x > 1) {
int m = (x+y+1)/2;
if (sg.get(0, 0, n-1, m, pos[dest]).maxi <= r) y = m;
else x = m;
}
// cout << i << " " << y << "\n";
res[i] = (sg.get(0, 0, n-1, pos[source], y).mini >= l and
sg.get(0, 0, n-1, y, pos[dest]).maxi <= r);
}
return res;
}
