#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct query
{
int l, r, s, e;
query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
{
l = _l;
r = _r;
s = _s;
e = _e;
}
} ask[maxn];
struct node_query
{
int idx, ver;
node_query(int _ver = 0, int _idx = 0)
{
ver = _ver;
idx = _idx;
}
};
int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];
vector < node_query > task[maxn];
const int maxlog = 21;
int fen[maxn];
int tour_pos[maxn], in[maxn], out[maxn];
void add(int p, int val)
{
for (int i = p; i < maxn; i += (i & -i))
fen[i] += val;
}
int sum(int p)
{
int s = 0;
for (int i = p; i > 0; i -= (i & -i))
s += fen[i];
return s;
}
vector < int > ans;
struct reconstruction_tree
{
vector < int > par, tin, tout, sub;
vector < vector < int > > adj;
vector < vector < int > > dp;
int timer;
reconstruction_tree(int n)
{
timer = 0;
tin.resize(n);
tout.resize(n);
par.resize(n);
adj.resize(n);
sub.resize(n);
dp.resize(maxlog);
for (int i = 0; i < maxlog; i ++)
dp[i].resize(n);
for (int i = 0; i < n; i ++)
{
par[i] = i;
}
}
void euler(int v, int par, bool type)
{
dp[0][v] = par;
for (int j = 1; j < maxlog; j ++)
{
if (dp[j - 1][v] == -1)
{
dp[j][v] = -1;
continue;
}
dp[j][v] = dp[j - 1][dp[j - 1][v]];
}
tin[v] = ++ timer;
if (type == false)
{
tour_pos[v] = timer;
in[v] = timer;
}
sub[v] = 1;
for (int u : adj[v])
{
euler(u, v, type);
sub[v] += sub[u];
}
tout[v] = timer;
if (type == false)
{
out[v] = timer;
}
}
void add_dfs(int v, int val)
{
add(tour_pos[v], val);
for (int u : adj[v])
{
add_dfs(u, val);
}
}
void dfs(int v, int p, bool big)
{
int mx = -1;
for (int u : adj[v])
{
if (mx == -1 || sub[u] > sub[mx])
mx = u;
}
for (int u : adj[v])
{
if (u != mx)
dfs(u, v, false);
}
if (mx != -1)
dfs(mx, v, true);
for (int u : adj[v])
{
if (u != mx)
add_dfs(u, 1);
}
add(tour_pos[v], 1);
///answer queries
for (node_query cur : task[v])
{
if (sum(out[cur.ver]) - sum(in[cur.ver] - 1) > 0)
ans[cur.idx] = 1;
else
ans[cur.idx] = 0;
}
if (!big)
{
add_dfs(v, -1);
}
}
int find_leader(int v)
{
if (v == par[v])
return v;
return (par[v] = find_leader(par[v]));
}
bool unite(int v, int u)
{
v = find_leader(v);
u = find_leader(u);
if (v == u)
return false;
par[u] = v;
return true;
}
void add_vertex(int v, bool type)
{
for (int u : graph[v])
{
if (type == 0 && u > v)
continue;
if (type == 1 && u < v)
continue;
int ld = find_leader(u);
if (unite(v, u))
adj[v].push_back(ld);
}
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
q = L.size();
m = X.size();
for (int i = 0; i < q; i ++)
{
ask[i] = query(L[i], R[i], S[i], E[i]);
}
for (int i = 0; i < m; i ++)
{
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
reconstruction_tree max_tree(n), min_tree(n);
for (int i = 0; i < n; i ++)
{
min_tree.add_vertex(i, 0);
}
for (int i = n - 1; i >= 0; i --)
{
max_tree.add_vertex(i, 1);
}
min_tree.euler(n - 1, -1, false);
max_tree.euler(0, -1, true);
ans.resize(q, 0);
for (int i = 0; i < q; i ++)
{
int ver = ask[i].s;
for (int j = maxlog - 1; j >= 0; j --)
{
if (max_tree.dp[j][ver] != -1 && max_tree.dp[j][ver] >= ask[i].l)
ver = max_tree.dp[j][ver];
}
int to = ask[i].e;
for (int j = maxlog - 1; j >= 0; j --)
{
if (min_tree.dp[j][to] != -1 && min_tree.dp[j][to] <= ask[i].r)
to = min_tree.dp[j][to];
}
///cout << ver << " " << to << endl;
task[ver].push_back(node_query(to, i));
}
max_tree.dfs(0, -1, true);
return ans;
}
