#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
// as human, we can only reach other nodes such that the next node is either:
// - less than the current node
// - below Ri
// as wolf:
// - greater than the current node
// - above Li
// so every time in a path and we go leq or greq
// we can find bounds L R that allow this edge.
// generalize: there are edges that only certain bounds can take
// how do we query these edges and connectivity quickly?
// instead phrase it from one side
// only consider human
// process in increasing Ri
const int INF = 1e9;
struct segtree {
int n, t;
vector<pair<int, int>> tree;
segtree(vector<int> &a) {
n = a.size();
t = 1;
while (t < n) t <<= 1;
tree.assign(2*t, {INF, -INF});
for (int i = 0; i < n; i++) {
tree[t + i] = {a[i], a[i]};
}
for (int i = t-1; i >= 0; i--) {
tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
}
}
void update(int ind, int upd) {
int i = t + ind;
tree[i] = {upd, upd};
for (i >>= 1; i; i >>= 1) {
tree[i].first = min(tree[i<<1].first, tree[i<<1|1].first);
tree[i].second = max(tree[i<<1].second, tree[i<<1|1].second);
}
}
pair<int, int> query(int l, int r) {
l += t, r += t;
pair<int, int> res = {INF, -INF};
while (l <= r) {
if (l & 1) {
res.first = min(res.first, tree[l].first);
res.second = max(res.second, tree[l].second);
l++;
}
if (!(r & 1)) {
res.first = min(res.first, tree[r].first);
res.second = max(res.second, tree[r].second);
r--;
}
l >>= 1, r >>= 1;
}
return res;
}
};
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(), M = X.size();
vector<int> ans(Q);
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
// find ends then work
vector<int> id(N, 0), sweep;
int fir = 0, sec = -1;
auto dfs = [&](auto &&dfs, int u, int p) -> void {
sweep.push_back(u);
sec = u;
for (auto &v : adj[u]) {
if (v != p) {
id[v] = id[u] + 1;
dfs(dfs, v, u);
}
}
};
dfs(dfs, fir, -1);
swap(fir, sec);
sweep.clear();
id.assign(N, 0);
dfs(dfs, fir, -1);
// build segtree on this
segtree st(sweep);
auto left = [&](int idx, int cap, bool up) -> int {
int l = -1, r = idx;
while (r - l > 1) {
int m = (l+r) / 2;
auto q = st.query(m, idx);
int v = (up ? q.first : q.second);
if (up ? (v >= cap) : (v <= cap)) {
r = m;
} else {
l = m;
}
}
return r;
};
auto right = [&](int idx, int cap, bool up) -> int {
int l = idx, r = N;
while (r - l > 1) {
int m = (l+r) / 2;
auto q = st.query(idx, m);
int v = (up ? q.first : q.second);
if (up ? (v >= cap) : (v <= cap)) {
l = m;
} else {
r = m;
}
}
return l;
};
for (int i = 0; i < Q; i++) {
if (S[i] < L[i] or E[i] > R[i]) {
ans[i] = false;
continue;
}
int ps = id[S[i]], pe = id[E[i]];
int hl = left(ps, L[i], true);
int hr = right(ps, L[i], true);
int wl = left(pe, R[i], false);
int wr = right(pe, R[i], false);
bool ok = !(hr < wl or wr < hl);
ans[i] = ok;
}
return ans;
}
