// TODO: Do sweepline.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vi P;
const int BB = 22;
int find(int vv) {
if (P[vv] == vv) return vv;
return P[vv] = find(P[vv]);
}
vector<vi> G2;
vi ORD, ORD2, TIN, TOU, POS;
vector<vi> PR;
void dfs(int v, int p) {
PR[v][0] = p;
TIN[v] = ORD.size();
ORD.push_back(v);
for (int u : G2[v]) if (u != p) {
dfs(u, v);
}
TOU[v] = ORD.size()-1;
}
void generate_intervals(int N, vector<vi> G, vi K, vi V, vi O, bool rev,
vi& A, vi& L, vi& R) {
P.resize(2*N);
for (int i = 0; i < 2*N; ++i) P[i] = i;
G2.assign(2*N, vi(0));
for (int i : O) {
for (int v : G[i]) {
if ((rev && find(v) > i) || (!rev && find(v) < i)) {
G2[i].push_back(find(v));
G2[find(v)].push_back(i);
//cerr << "a" << i << ' ' << find(v) << '\n';
P[find(v)] = i;
}
}
}
ORD.clear();
ORD.reserve(N);
TIN.resize(N);
TOU.resize(N);
PR.assign(N, vi(BB));
dfs(O.back(), O.back());
int Q = V.size();
A = ORD;
L.resize(Q);
R.resize(Q);
for (int xx : A) {
//cerr << xx << ' ';
}
//cerr << '\n';
///
for (int b = 1; b < BB; ++b) {
for (int i = 0; i < N; ++i) {
PR[i][b] = PR[PR[i][b-1]][b-1];
}
}
for (int k = 0; k < Q; ++k) {
int vv = K[k];
if (!((rev && vv >= V[k]) || (!rev && vv <= V[k]))) {
L[k] = 0;
R[k] = -1;
//cerr << ' ' << L[k] << ' ' << R[k] << '\n';
continue;
}
for (int b = BB-1; b >= 0; --b) {
int nv = PR[vv][b];
if ((rev && nv >= V[k]) || (!rev && nv <= V[k])) vv = nv;
}
L[k] = TIN[vv];
R[k] = TOU[vv];
//cerr << ' ' << L[k] << ' ' << R[k] << '\n';
}
}
vi FT;
int lsb(int x) {
return x&(-x);
}
void ch(int p, int v) {
++p;
while (p < FT.size()) {
FT[p] += v;
p += lsb(p);
}
}
int rsq(int p) {
++p;
int v = 0;
while (p) {
v += FT[p];
p -= lsb(p);
}
return v;
}
int rsq(int l, int r) {
return rsq(r)-rsq(l-1);
}
vi check_validity(int N, vi X, vi Y,
vi S, vi E,
vi L, vi R) {
vector<vi> G(N);
for (int i = 0; i < X.size(); ++i) {
G[X[i]].push_back(Y[i]);
G[Y[i]].push_back(X[i]);
}
vi O(N);
for (int i = 0; i < N; ++i) O[i] = i;
vi A, LA, RA;
generate_intervals(N, G, E, R, O, 0, A, LA, RA);
reverse(O.begin(), O.end());
vi B, LB, RB;
generate_intervals(N, G, S, L, O, 1, B, LB, RB);
vi IB(N);
for (int i = 0; i < N; ++i) IB[B[i]] = i;
int Q = S.size();
vi ANS(Q, 0);
FT.assign(N+1, 0);
vector<pair<int, int>> QS;
for (int k = 0; k < Q; ++k) {
QS.push_back({LA[k]-1, -k-1});
QS.push_back({RA[k], +k});
}
//cerr << "H";
sort(QS.begin(), QS.end());
int cidx = -1;
for (auto [aa, bb] : QS) {
int cv = +1;
if (bb < 0) {
bb = -1-bb;
cv = -1;
}
while (cidx < aa) {
++cidx;
ch(IB[A[cidx]], +1);
}
ANS[bb] += cv*rsq(LB[bb], RB[bb]);
}
for (int i = 0; i < Q; ++i) {
//cerr << ANS[i] << '\n';
ANS[i] = min(ANS[i], 1);
}
return ANS;
}
