#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<vector<int>> g;
vector<int> link;
vector<int> euler, l, r;
DSU(int n) {
g.resize(n), link.resize(n);
l.resize(n), r.resize(n);
iota(link.begin(), link.end(), 0);
}
int getP(int x) {
if (link[x] == x) return x;
return link[x] = getP(link[x]);
}
void unite(int dad, int son) {
dad = getP(dad), son = getP(son);
if (dad == son) return;
link[son] = dad;
g[dad].push_back(son);
}
void dfs(int v) {
l[v] = euler.size();
euler.push_back(v);
for (int u : g[v])
dfs(u);
r[v] = euler.size();
}
};
struct MST {
vector<vector<int>> t;
MST(vector<int>& a) {
t.resize(a.size() * 4);
build(0, 0, a.size(), a);
}
void build(int v, int tl, int tr, vector<int>& a) {
if (tl + 1 == tr) {
t[v].push_back(a[tl]);
return;
}
int m = (tl + tr) / 2;
build(2 * v + 1, tl, m, a);
build(2 * v + 2, m, tr, a);
t[v].resize(t[2 * v + 1].size() + t[2 * v + 2].size());
merge(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[2 * v + 2].begin(), t[2 * v + 2].end(), t[v].begin());
}
int get(int v, int tl, int tr, int l, int r, int lo, int hi) {
if (tl >= r || tr <= l)
return 0;
if (tl >= l && tr <= r) {
return lower_bound(t[v].begin(), t[v].end(), hi) - lower_bound(t[v].begin(), t[v].end(), lo);
}
int m = (tl + tr) / 2;
return get(2 * v + 1, tl, m, l, r, lo, hi) + get(2 * v + 2, m, tr, l, r, lo, hi);
}
};
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(), q = S.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++)
g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
vector<vector<int>> le(n), re(n);
for (int i = 0; i < q; i++)
le[L[i]].push_back(i), re[R[i]].push_back(i);
vector<int> lp(q);
DSU dl(n);
for (int i = n - 1; i >= 0; i--) {
for (int j : g[i])
if (j > i)
dl.unite(i, j);
for (int ind : le[i])
lp[ind] = dl.getP(S[ind]);
}
int dl_root = dl.getP(0);
dl.dfs(dl_root);
vector<int> rp(q);
DSU dr(n);
for (int i = 0; i < n; i++) {
for (int j : g[i])
if (j < i)
dr.unite(i, j);
for (int ind : re[i])
rp[ind] = dr.getP(E[ind]);
}
int dr_root = dr.getP(0);
dr.dfs(dr_root);
vector<int> p_dl(n);
for (int i = 0; i < n; i++)
p_dl[dl.euler[i]] = i;
vector<int> a(n);
for (int i = 0; i < n; i++)
a[i] = p_dl[dr.euler[i]];
vector<int> ans(q);
MST t(a);
for (int i = 0; i < q; i++) {
int l1 = dl.l[lp[i]], r1 = dl.r[lp[i]];
int l2 = dr.l[rp[i]], r2 = dr.r[rp[i]];
int x = t.get(0, 0, n, l2, r2, l1, r1);
ans[i] = x > 0;
}
return ans;
}
