#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N, Q, M;
vi S, E, L, R;
vvi adj;
vvi Eadj, Sadj;
vi Ein, Eout, Sin, Sout;
vvi Elift, Slift;
vi depth;
int idx;
struct unionfind
{
vi arr;
void init(int size)
{
arr.resize(size);
iota(all(arr), 0);
}
int find(int i) { return arr[i] = (arr[i] == i) ? i : find(arr[i]); }
void combine(int a, int b)
{
// a is the one it gets merged to
a = find(a), b = find(b);
arr[b] = a;
}
};
unionfind uf;
void dfs(vvi &A, int v, int p, vi &in, vi &out, vvi &lift)
{
in[v] = idx++;
lift[v][0] = p;
for (int j = 1; j < sz(lift[v]); ++j)
lift[v][j] = lift[lift[v][j - 1]][j - 1];
for (int u : A[v])
if (u != p)
dfs(A, u, v, in, out, lift);
out[v] = idx++;
}
bool is_vorg(int a, int b, vi &in, vi &out)
{
return in[a] <= in[b] && out[b] <= out[a];
}
vvpii tocheck; // [e] := list of s values with whom the subtree comparison should work
vector<set<int>> nodes; // [e] := set of all invalues my nodes have in S
vi A; // the answer
void answer(int v, int p)
{
// going through e per definition
nodes[v].insert(Sin[v]);
for (int u : Eadj[v])
if (u != p)
{
answer(u, v);
if (sz(nodes[u]) > sz(nodes[v]))
swap(nodes[u], nodes[v]);
for (int x : nodes[u])
nodes[v].insert(x);
}
for (pii tmp : tocheck[v])
{
int s, q;
tie(s, q) = tmp;
auto it = nodes[v].lower_bound(Sin[s]);
if (it == nodes[v].end())
A[q] = 0;
else
{
int lb = *it;
assert(lb >= Sin[s]);
A[q] = (lb < Sout[s]);
}
}
}
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)
{
N = _N, Q = sz(_S), M = sz(X);
S = _S, E = _E, L = _L, R = _R;
adj.assign(N, vi());
for (int i = 0; i < M; ++i)
adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
Eadj.assign(N, vi());
uf.init(N);
for (int v = 0; v < N; ++v)
{
for (int u : adj[v])
if (u < v)
{
u = uf.find(u);
if (u != v)
Eadj[v].push_back(u), uf.combine(v, u);
}
}
idx = 0;
Ein.resize(N), Eout.resize(N);
Elift.assign(N, vi(ceil(log2(N))));
dfs(Eadj, N - 1, N - 1, Ein, Eout, Elift);
Sadj.assign(N, vi());
uf.init(N);
for (int v = N - 1; v >= 0; --v)
{
for (int u : adj[v])
if (u > v)
{
u = uf.find(u);
if (u != v)
Sadj[v].push_back(u), uf.combine(v, u);
}
}
idx = 0;
Sin.resize(N), Sout.resize(N);
Slift.assign(N, vi(ceil(log2(N))));
dfs(Sadj, 0, 0, Sin, Sout, Slift);
tocheck.assign(N, vpii());
for (int q = 0; q < Q; ++q)
{
int Enode = E[q];
for (int j = sz(Elift[Enode]) - 1; j >= 0; --j)
if (Elift[Enode][j] <= R[q])
Enode = Elift[Enode][j];
int Snode = S[q];
for (int j = sz(Slift[Snode]) - 1; j >= 0; --j)
if (Slift[Snode][j] >= L[q])
Snode = Slift[Snode][j];
tocheck[Enode].push_back({Snode, q});
}
A.assign(Q, 0);
nodes.assign(N, set<int>());
answer(N - 1, N - 1);
return A;
}
