#include "werewolf.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int maxN = 200'005;
struct Quer {
int l, r, s, e, ind, link1, link2;
};
int n;
vector<int> ans;
vector<Quer> quer, withLink1[maxN * 2];
vector<int> nei[maxN], nei1[maxN * 2], nei2[maxN * 2];
set<int> t[maxN * 2];
int col[maxN], linkl[maxN * 2], linkr[maxN * 2];
struct DSU
{
vector<int> par, sz, link;
DSU(int n)
: par(n)
, sz(n)
, link(n)
{
for (int i = 0; i < n; ++i)
par[i] = link[i] = i, sz[i] = 1;
}
int root(int v) {
return v == par[v] ? v : par[v] = root(par[v]);
}
void unite(int u, int v, int curLink) {
u = root(u); v = root(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
par[u] = v;
link[v] = curLink;
}
};
void DFS(int v)
{
static int time = -1;
linkl[v] = time + 1;
if (nei2[v].empty())
col[v] = ++time;
for (int to: nei2[v])
{
// cerr << v << " -> " << to << '\n';
DFS(to);
}
linkr[v] = time;
}
int Color1()
{
DSU dsu(n);
int nodes = n;
sort(quer.begin(), quer.end(), [](const Quer& l, const Quer& r) {
return l.l < r.l;
});
for (int v = n - 1, i = (int)quer.size() - 1; v >= 0; --v)
{
nei1[nodes].push_back(dsu.link[dsu.root(v)]);
for (int to: nei[v])
{
if (to < v) continue;
if (dsu.root(v) == dsu.root(to))
continue;
nei1[nodes].push_back(dsu.link[dsu.root(to)]);
dsu.unite(v, to, nodes);
}
while (i >= 0 && quer[i].l == v) {
quer[i].link1 = dsu.link[dsu.root(quer[i].s)];
--i;
}
++nodes;
}
return nodes - 1;
}
void Color2()
{
DSU dsu(n);
int nodes = n;
sort(quer.begin(), quer.end(), [](const Quer& l, const Quer& r) {
return l.r > r.r;
});
for (int v = 0, i = (int)quer.size() - 1; v < n; ++v)
{
int b = -1;
nei2[nodes].push_back(b = dsu.link[dsu.root(v)]);
for (int to: nei[v])
{
if (to > v) continue;
if (dsu.root(v) == dsu.root(to))
continue;
nei2[nodes].push_back(b = dsu.link[dsu.root(to)]);
dsu.unite(v, to, nodes);
}
while (i >= 0 && quer[i].r == v) {
quer[i].link2 = dsu.link[dsu.root(quer[i].e)];
--i;
}
++nodes;
}
DFS(nodes - 1);
}
void Solve(int v)
{
if (nei1[v].empty())
t[v].insert(col[v]);
for (int to: nei1[v])
{
Solve(to);
if (t[v].size() < t[to].size())
t[v].swap(t[to]);
t[v].insert(t[to].begin(), t[to].end());
}
for (Quer& q: withLink1[v])
{
auto it = t[v].lower_bound(linkl[q.link2]);
if (it != t[v].end() && *it <= linkr[q.link2])
ans[q.ind] = 1;
}
}
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;
quer.resize(S.size());
for (int i = 0; i < S.size(); ++i)
{
quer[i].s = S[i];
quer[i].e = E[i];
quer[i].l = L[i];
quer[i].r = R[i];
quer[i].ind = i;
}
for (int i = 0; i < X.size(); ++i)
{
int u = X[i], v = Y[i];
nei[u].push_back(v);
nei[v].push_back(u);
}
int root = Color1();
Color2();
ans.resize(quer.size());
for (Quer& q: quer)
withLink1[q.link1].push_back(q);
Solve(root);
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
