#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
vt<int> check_validity(int N, vt<int> X, vt<int> Y, vt<int> S, vt<int> E, vt<int> L, vt<int> R) {
vt<int> adj[N];
FOR(i, 0, size(X)-1) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
auto gen_tree = [&](int mul) {
int uf[N], mx[N];
memset(uf, -1, sizeof(uf));
FOR(i, 0, N-1)
mx[i] = i * mul;
function<int(int)> find = [&](int i) {
return uf[i] < 0 ? i : uf[i] = find(uf[i]);
};
vt<vt<int>> tree(N);
auto unite = [&](int a, int b) {
if ((a = find(a)) == (b = find(b)))
return false;
if (uf[a] > uf[b])
swap(a, b);
tree[mul * max(mx[a], mx[b])].push_back(mul * min(mx[a], mx[b]));
uf[a] += uf[b];
uf[b] = a;
mx[a] = max(mx[a], mx[b]);
return true;
};
REP(i, ~mul ? 0 : N-1, ~mul ? N-1 : 0, mul)
for (int j : adj[i])
if (j * mul < i * mul)
unite(i, j);
return tree;
};
vt<vt<int>> wt = gen_tree(1); // root is N-1
vt<vt<int>> ht = gen_tree(-1); // root is 0
int tin[N], tout[N], lift_ht[N][18], lift_wt[N][18], timer = 0;
function<void(int, int)> dfs_ht = [&](int i, int p) {
tin[i] = timer++;
lift_ht[i][0] = p;
for (int j : ht[i])
dfs_ht(j, i);
tout[i] = timer - 1;
};
function<void(int, int)> dfs_wt = [&](int i, int p) {
lift_wt[i][0] = p;
for (int j : wt[i])
dfs_wt(j, i);
};
dfs_ht(0, 0);
dfs_wt(N-1, N-1);
FOR(j, 1, 17)
FOR(i, 0, N-1) {
lift_wt[i][j] = lift_wt[lift_wt[i][j-1]][j-1];
lift_ht[i][j] = lift_ht[lift_ht[i][j-1]][j-1];
}
// S in ht
// E in wt
vt<ari2> Q[N];
FOR(i, 0, size(S)-1) {
// find maximum ancestor of E[i]
int a = E[i];
ROF(j, 17, 0)
if (lift_wt[a][j] <= R[i])
a = lift_wt[a][j];
// find minimum ancestor of S[i]
int b = S[i];
ROF(j, 17, 0)
if (lift_ht[b][j] >= L[i])
b = lift_ht[b][j];
Q[a].push_back({b, i});
}
vt<int> ans(size(S));
set<int> ss[N];
function<void(int)> dfs = [&](int i) {
ss[i].insert(tin[i]);
for (int j : wt[i]) {
dfs(j);
if (size(ss[j]) > size(ss[i]))
swap(ss[j], ss[i]);
for (int v : ss[j])
ss[i].insert(v);
ss[j].clear();
}
for (auto [j, q] : Q[i])
ans[q] = ss[i].lower_bound(tin[j]) != ss[i].upper_bound(tout[j]);
};
dfs(N-1);
return ans;
}
