#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> g[200000];
int par1[200000][20], par2[200000][20];
int e[200000];
int find(int u)
{
return e[u] == u ? u : e[u] = find(e[u]);
}
int euler1[200000];
int in1[200000] = {0}, out1[200000] = {0}, t1 = 0;
int in2[200000] = {0}, out2[200000] = {0}, t2 = 0;
vector<int> c1[200000], c2[200000];
void dfs1(int u)
{
in1[u] = t1++;
euler1[in1[u]] = u;
for (int v : c1[u])
dfs1(v);
out1[u] = t1;
}
void dfs2(int u)
{
in2[u] = t2++;
for (int v : c2[u])
dfs2(v);
out2[u] = t2;
}
struct Event
{
int l, r, t, i;
};
vector<Event> events[200000];
int t[200000] = {0};
void update(int N, int idx, int val)
{
for (; idx < N; idx |= (idx + 1))
t[idx] += val;
}
int quer(int r)
{
int res = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
res += t[r];
return res;
}
int query(int l, int r)
{
return quer(r) - quer(l - 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)
{
int Q = S.size(), M = X.size();
vector<int> A(Q, 0);
int K = 0;
while ((1 << K) < N) K++;
for (int i = 0; i < N; i++)
par1[i][0] = par2[i][0] = i;
for (int i = 0; i < M; i++)
{
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
iota(e, e + N, 0);
for (int u = 0; u < N; u++)
for (int v : g[u])
if (v < u)
{
v = find(v);
e[v] = u;
par1[v][0] = u;
}
iota(e, e + N, 0);
for (int u = N - 1; u >= 0; u--)
for (int v : g[u])
if (v > u)
{
v = find(v);
e[v] = u;
par2[v][0] = u;
}
for (int k = 1; k <= K; k++)
for (int u = 0; u < N; u++)
{
par1[u][k] = par1[par1[u][k-1]][k-1];
par2[u][k] = par2[par2[u][k-1]][k-1];
}
for (int i = 0; i < N; i++)
{
if (par1[i][0] != i)
c1[par1[i][0]].push_back(i);
if (par2[i][0] != i)
c2[par2[i][0]].push_back(i);
}
for (int i = N - 1; i >= 0; i--)
if (!in1[i])
dfs1(i);
for (int i = 0; i < N; i++)
if (!in2[i])
dfs2(i);
for (int i = 0; i < Q; i++)
{
for (int k = K; k >= 0; k--)
{
if (par1[E[i]][k] <= R[i])
E[i] = par1[E[i]][k];
if (par2[S[i]][k] >= L[i])
S[i] = par2[S[i]][k];
}
}
for (int i = 0; i < Q; i++)
events[out1[E[i]]-1].push_back({in2[S[i]], out2[S[i]]-1, 1, i});
for (int i = 0; i < Q; i++)
events[in1[E[i]]-1].push_back({in2[S[i]], out2[S[i]]-1, -1, i});
for (int idx = 0; idx < N; idx++)
{
update(N, in2[euler1[idx]], 1);
for (auto &[l, r, t, i] : events[idx])
A[i] += t * query(l, r);
}
for (int &x : A)
x = (x > 0);
return A;
}
