#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5, lg = 19;
int n, q;
vector<int> edge[Nmax];
int node_A[Nmax], node_B[Nmax];
vector<pair<int,int>> when[Nmax];
struct Arb
{
vector<int> son[Nmax];
int L[Nmax], R[Nmax], tmp = 0;
int root;
int up[lg+2][Nmax];
void dfs(int node, int dad = -1)
{
L[node] = ++tmp;
up[0][node] = dad;
int i;
for(i=1; up[i-1][node] != -1; ++i)
up[i][node] = up[i-1][up[i-1][node]];
for(; i<=lg; ++i) up[i][node] = -1;
for(auto it : son[node])
dfs(it, node);
R[node] = tmp;
}
} A, B;
struct Forest
{
int t[Nmax];
int boss(int x)
{
if(x == t[x]) return x;
return t[x] = boss(t[x]);
}
void init()
{
int i;
for(i=0; i<n; ++i) t[i] = i;
}
bool unite(int x, int y)
{
if(x == y) return 0;
t[y] = x;
return 1;
}
} forest;
auto MinSort = [] (int x, int y) { return x < y; };
auto MaxSort = [] (int x, int y) { return x > y; };
void build_tree(Arb &A, function<bool(int, int)> cmp)
{
vector<int> ord;
int i;
for(i=0; i<n; ++i) ord.push_back(i);
sort(ord.begin(), ord.end(), cmp);
forest.init();
for(auto node : ord)
for(auto it : edge[node])
if(cmp(it, node))
{
int who = forest.boss(it);
if(who == node) continue;
A.son[node].push_back(who);
forest.t[who] = node;
}
A.root = ord.back();
A.dfs(A.root);
}
int fnd(Arb &A, int node, int lim, function<bool (int, int)> cmp)
{
int i;
for(i=lg; i>=0; --i)
if(A.up[i][node] != -1 && cmp(A.up[i][node], lim)) node = A.up[i][node];
return node;
}
void find_queries(vector<int> &S, vector<int> &E, vector<int> &L, vector<int> &R)
{
int i;
for(i=0; i<q; ++i)
{
node_A[i] = fnd(A, S[i], L[i] - 1, MaxSort);
node_B[i] = fnd(B, E[i], R[i] + 1, MinSort);
}
}
set<int> s[Nmax];
int w[Nmax];
vector<int> ans;
void dfs(int node)
{
w[node] = 1;
for(auto it : A.son[node])
{
dfs(it);
w[node] += w[it];
}
int xson = -1;
for(auto it : A.son[node])
if(xson == -1 || w[it] > w[xson]) xson = it;
if(xson != -1) swap(s[node], s[xson]);
for(auto it : A.son[node])
if(it != xson)
for(auto x : s[it])
s[node].insert(x);
s[node].insert(B.L[node]);
for(auto it : when[node])
{
int bnode, id;
tie(bnode, id) = it;
set<int> :: iterator itt = s[node].lower_bound(B.L[bnode]);
if(itt != s[node].end() && *itt <= B.R[bnode])
ans[id] = 1;
else ans[id] = 0;
}
}
void solve_queries()
{
int i;
for(i=0; i<q; ++i)
when[node_A[i]].push_back({ node_B[i], i });
dfs(A.root);
}
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 = S.size();
ans.resize(q);
int i;
for(i=0; i<X.size(); ++i)
{
edge[X[i]].push_back(Y[i]);
edge[Y[i]].push_back(X[i]);
}
build_tree(A, MaxSort);
build_tree(B, MinSort);
find_queries(S, E, L, R);
solve_queries();
return ans;
}
