#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
const int MAXP = 18;
vector<int> adj[MAXN], adjMin[MAXN], adjMax[MAXN];
vector<int> S, E;
int tin[MAXN], tout[MAXN];
int curTime;
int parMin[MAXP][MAXN], parMax[MAXP][MAXN];
int nbSommets, nbAretes, nbRequetes;
vector<int> ans;
vector<int> queryAtNode[MAXN];
int idMin[MAXN], largestMin[MAXN], idMax[MAXN], smallestMax[MAXN];
void dfs(int u) {
tin[u] = curTime++;
for (int v : adjMin[u])
dfs(v);
tout[u] = curTime++;
}
set<int> dfs2(int u) {
vector<set<int>> childs = {{tin[u]}};
for (int v : adjMax[u]) {
childs.push_back(dfs2(v));
}
for (int i = 1; i < (int)childs.size(); ++i)
if (childs[i].size() > childs[0].size())
swap(childs[i], childs[0]);
for (int i = 1; i < (int)childs.size(); ++i)
for (auto v : childs[i])
childs[0].insert(v);
set<int> ret = move(childs[0]);
for (int iRequete : queryAtNode[u]) {
auto it = ret.lower_bound(tin[S[iRequete]]);
if (it != ret.end() and *it <= tout[S[iRequete]])
ans[iRequete] = 1;
}
return ret;
}
// Min tree : We want the minimum vertex on a path to be the largest possible.
int findMin(int u) { return idMin[u] < 0 ? u : idMin[u] = findMin(idMin[u]); }
int findMax(int u) { return idMax[u] < 0 ? u : idMax[u] = findMax(idMax[u]); }
void mergeMin(int a, int b) {
a = findMin(a), b = findMin(b);
if (a == b)
return;
if (largestMin[a] < largestMin[b])
swap(a, b);
parMin[0][largestMin[a]] = largestMin[b];
adjMin[largestMin[b]].push_back(largestMin[a]);
idMin[a] += idMin[b];
idMin[b] = a;
largestMin[a] = largestMin[b];
}
void mergeMax(int a, int b) {
a = findMax(a), b = findMax(b);
if (a == b)
return;
if (smallestMax[a] > smallestMax[b])
swap(a, b);
parMax[0][smallestMax[a]] = smallestMax[b];
adjMax[smallestMax[b]].push_back(smallestMax[a]);
idMax[a] += idMax[b];
idMax[b] = a;
smallestMax[a] = smallestMax[b];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> _S,
vector<int> _E, vector<int> L, vector<int> R) {
S = _S, E = _E;
nbSommets = N;
nbAretes = X.size();
for (int i = 0; i < nbAretes; ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < nbSommets; ++i) {
largestMin[i] = smallestMax[i] = i;
idMin[i] = idMax[i] = -1;
}
for (int i = nbSommets - 1; i >= 0; --i)
for (int j : adj[i])
if (j > i) {
mergeMin(j, i);
}
for (int i = 0; i < nbSommets; ++i)
for (int j : adj[i])
if (j < i)
mergeMax(j, i);
parMax[0][nbSommets - 1] = nbSommets - 1;
for (int p = 0; p < MAXP - 1; ++p)
for (int i = 0; i < nbSommets; ++i) {
parMax[p + 1][i] = parMax[p][parMax[p][i]];
parMin[p + 1][i] = parMin[p][parMin[p][i]];
}
nbRequetes = S.size();
for (int i = 0; i < nbRequetes; ++i)
for (int p = MAXP - 1; p >= 0; --p)
if (parMin[p][S[i]] >= L[i])
S[i] = parMin[p][S[i]];
ans.resize(nbRequetes);
for (int i = 0; i < nbRequetes; ++i)
for (int p = MAXP - 1; p >= 0; --p)
if (parMax[p][E[i]] <= R[i])
E[i] = parMax[p][E[i]];
for (int i = 0; i < nbRequetes; ++i)
queryAtNode[E[i]].push_back(i);
dfs(0);
dfs2(nbSommets - 1);
return ans;
}
