#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
struct Edge {
int u, v, w;
bool operator<(const Edge &other) const {
return w < other.w;
}
};
// we need dsu to find the root of node u's current component
struct DSU {
int n;
vector<int> par, size;
DSU(int N) {
n = N;
par.assign(n, 0); iota(par.begin(), par.end(), 0);
size.assign(n, 1);
}
DSU() : n(0) {};
int find_set(int v) {
if (par[v] == v) {
return v;
}
return par[v] = find_set(par[v]);
}
void unite(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
// if (size[a] < size[b]) swap(a, b); // no union by rank though
par[b] = a;
size[a] += size[b];
}
}
};
struct DSUTree {
int n, m, k; // n = original graph size, m = num edges, k = 2n-1 = kruskal tree size
DSU dsu;
vector<vector<int>> adj; // adjlist for dsu tree
vector<int> value, edgeid; // value of node i (0 for all leaves)
vector<Edge> edge_list;
int MAXLOG;
vector<vector<int>> up;
int timer;
vector<int> tin, tout;
DSUTree(int N, vector<Edge> edges) {
n = N;
m = edges.size();
k = 2 * n - 1;
edge_list = edges;
dsu = DSU(k);
adj.assign(k, vector<int>());
value.assign(k, 0);
edgeid.assign(k, 0);
construct();
}
void dfs(int u, int p) {
tin[u] = timer++;
up[u][0] = p;
for (int i = 1; i < MAXLOG; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (auto &v : adj[u]) {
if (v == p) continue;
dfs(v, u);
}
tout[u] = timer;
}
void construct() {
sort(edge_list.begin(), edge_list.end());
int cur_anc = n; // who shall we set the ancestor of u and v to for the current merge
for (int i = 0; i < m; i++) {
Edge cur = edge_list[i];
int u = cur.u, v = cur.v, w = cur.w;
int uhead = dsu.find_set(u), vhead = dsu.find_set(v);
if (uhead != vhead) {
dsu.unite(cur_anc, uhead);
dsu.unite(cur_anc, vhead);
adj[cur_anc].push_back(uhead);
adj[cur_anc].push_back(vhead);
adj[uhead].push_back(cur_anc);
adj[vhead].push_back(cur_anc);
value[cur_anc] = w;
edgeid[cur_anc] = i;
cur_anc++;
}
}
MAXLOG = 0;
while (k >= (1 << MAXLOG)) MAXLOG++;
up.assign(k, vector<int>(MAXLOG, 0));
tin.assign(k, 0);
tout.assign(k, 0);
timer = 0;
dfs(dsu.find_set(0), dsu.find_set(0));
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = MAXLOG - 1; i >= 0; i++) {
if (!is_ancestor(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
int query_pathmax(int u, int v) { // max edge on path from u to v
int anc = lca(u, v);
return value[anc];
}
bool can_reach(int u, int v, int x) { // can i reach v from u in first x nodes
return edgeid[lca(u, v)] < x;
}
};
struct Node {
Node *left, *right;
int sum;
Node(int val) : left(nullptr), right(nullptr), sum(val) {};
Node(Node* L, Node* R) {
left = L;
right = R;
sum = 0;
if (left) sum += left->sum;
if (right) sum += right->sum;
}
};
struct SegTree {
int n;
vector<Node*> roots;
vector<int> arr;
Node* build(int l, int r) {
if (l + 1 == r) return new Node(arr[l]);
int m = l + (r - l) / 2;
return new Node(build(l, m), build(m, r));
}
Node* update(Node *current, int l, int r, int k, int v) {
if (!(l <= k && k < r)) return current;
if (l + 1 == r) return new Node(v);
int m = l + (r - l) / 2;
return new Node(update(current->left, l, m, k, v), update(current->right, m, r, k, v));
}
int query(Node *current, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return 0;
if (ql <= l && r <= qr) return current->sum;
int m = l + (r - l) / 2;
return query(current->left, l, m, ql, qr) + query(current->right, m, r, ql, qr);
}
void update(int k, int v) {
roots.push_back(update(roots.back(), 0, n, k, v));
}
int query(int l, int r, int time) {
return query(roots[time], 0, n, l, r);
}
SegTree(int n, vector<int> arr) {
this->n = n;
this->arr = arr;
roots.push_back(build(0, n));
}
};
/*
N = num nodes
X, Y = edges
S, E = start and end nodes
L, R = human and werewolf cities
*/
int n, m, q;
vi x, y, s, e, l, r;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int n = N, m = X.size(), q = S.size();
// 1) Build two KRTs:
// DLo for “≤ R” uses w = max(u,v)
// DHi for “≥ L” uses w = -min(u,v)
vector<Edge> edges_lo(m), edges_hi(m);
FOR(i,0,m) {
int u = X[i], v = Y[i];
edges_lo[i] = {u, v, max(u,v)};
edges_hi[i] = {u, v, -min(u,v)};
}
DSUTree DLo(n, edges_lo);
DSUTree DHi(n, edges_hi);
int K = 2*n - 1;
auto &tin_lo = DLo.tin;
auto &tout_lo = DLo.tout;
auto &tin_hi = DHi.tin;
auto &tout_hi = DHi.tout;
// 2) Collect each city as a point (x = tin_hi, y = tin_lo)
vector<pair<int,int>> pts(n);
FOR(i,0,n) pts[i] = { tin_hi[i], tin_lo[i] };
sort(all(pts));
// 3) Build events: for each query we need to test if
// any point lies in [a,b)×[c,d). We'll do two events
// at x=b-1 (+1) and x=a-1 (−1).
struct Event { int x, y1, y2, idx, sign; };
vector<Event> events; events.reserve(2*q);
FOR(i,0,q) {
int Si = S[i], Ei = E[i], Li = L[i], Ri = R[i];
// climb DHi so that all merges along S→u have w ≤ -L ⇔ min(vertex) ≥ L
int thresh_hi = -Li;
int u = Si;
for (int d = DHi.MAXLOG-1; d >= 0; d--) {
int vup = DHi.up[u][d];
if (DHi.value[vup] <= thresh_hi) u = vup;
}
int a = tin_hi[u], b = tout_hi[u];
// climb DLo so that all merges along E→v have w ≤ R ⇔ max(vertex) ≤ R
int thresh_lo = Ri;
int v = Ei;
for (int d = DLo.MAXLOG-1; d >= 0; d--) {
int vup = DLo.up[v][d];
if (DLo.value[vup] <= thresh_lo) v = vup;
}
int c = tin_lo[v], d2 = tout_lo[v];
events.push_back({b-1, c, d2, i, +1});
events.push_back({a-1, c, d2, i, -1});
}
sort(all(events), [&](auto &A, auto &B){ return A.x < B.x; });
// 4) Fenwick tree over y in [0..K)
vector<int> bit(K+1, 0);
auto bit_add = [&](int pos, int v) {
for (int i = pos+1; i <= K; i += i&-i)
bit[i] += v;
};
auto bit_sum = [&](int pos) {
int s = 0;
for (int i = pos; i > 0; i -= i&-i)
s += bit[i];
return s;
};
auto bit_range = [&](int lpos, int rpos) {
if (lpos >= rpos) return 0;
return bit_sum(rpos) - bit_sum(lpos);
};
// 5) Sweep
vi acc(q, 0);
int ptr = 0;
for (auto &ev : events) {
// add all points with x ≤ ev.x
while (ptr < n && pts[ptr].first <= ev.x) {
bit_add(pts[ptr].second, +1);
ptr++;
}
int cnt = bit_range(ev.y1, ev.y2);
acc[ev.idx] += ev.sign * cnt;
}
// 6) any positive → reachable
vi ans(q);
FOR(i,0,q) ans[i] = (acc[i] > 0);
return ans;
}
