#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <functional>
using namespace std;
struct DSU
{
int N;
vector<int> A;
DSU(int _N = 0): N(_N), A(N, -1) {};
int get(int u) { return (A[u] < 0 ? u : A[u] = get(A[u])); }
void set(int v, int u) { A[get(v)] = u; }
};
struct BIT
{
int N;
vector<int> A;
BIT(int _N = 0): N(_N + 5), A(N, 0) {};
void inc(int i)
{
for (; i < N; i += i & (-i)) ++A[i];
}
int get(int l, int r)
{
int ans = 0;
for (--l; l > 0; l -= l & (-l)) ans -= A[l];
for (; r > 0; r -= r & (-r)) ans += A[r];
return ans;
}
};
struct Tree : vector<vector<int>>
{
int LG, N;
vector<vector<int>> anc;
Tree(int _N): N(_N) { assign(N, vector<int>()); }
void build()
{
LG = __lg(N) + 1;
anc.assign(LG, vector<int>(N, -1));
for (int u = 0; u < N; ++u) for (int v : at(u)) anc[0][v] = u;
for (int j = 1; j < LG; ++j) for (int u = 0; u < N; ++u) {
anc[j][u] = (~anc[j - 1][u] ? anc[j - 1][anc[j - 1][u]] : -1);
}
}
void findTour(int u, int &curTime, vector<int> &tin, vector<int> &tout)
{
tin[u] = ++curTime;
for (int v : at(u)) findTour(v, curTime, tin, tout);
tout[u] = curTime;
}
void solve(int u, BIT &bit, vector<vector<pair<int, int>>> &queries, vector<int> &ans, vector<int> &tin, vector<int> &tout)
{
for (auto &q : queries[u]) ans[q.second] = -bit.get(tin[q.first], tout[q.first]);
bit.inc(tin[u]);
for (int v : at(u)) solve(v, bit, queries, ans, tin, tout);
for (auto &q : queries[u]) ans[q.second] += bit.get(tin[q.first], tout[q.first]);
}
};
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 M = (int) X.size(), Q = (int) S.size();
vector<vector<int>> adj(N);
for (int i = 0; i < M; ++i) adj[X[i]].push_back(i), adj[Y[i]].push_back(i);
Tree startTree(N), finishTree(N);
DSU dsu;
dsu = DSU(N);
for (int u = N - 1; u >= 0; --u) {
for (int i : adj[u]) {
int v = u ^ X[i] ^ Y[i];
if (v > u) {
if (dsu.get(v) == u) continue;
// cout << "sta " << u << " -> " << dsu.get(v) << endl;
startTree[u].push_back(dsu.get(v));
dsu.set(v, u);
}
}
}
dsu = DSU(N);
for (int u = 0; u < N; ++u) {
for (int i : adj[u]) {
int v = u ^ X[i] ^ Y[i];
if (v < u) {
if (dsu.get(v) == u) continue;
// cout << "fin " << u << " -> " << dsu.get(v) << endl;
finishTree[u].push_back(dsu.get(v));
dsu.set(v, u);
}
}
}
finishTree.build(), startTree.build();
vector<int> tin(N), tout(N);
int curTime = 0;
startTree.findTour(0, curTime, tin, tout);
vector<vector<pair<int, int>>> queries(N);
for (int q = 0; q < Q; ++q) {
// cout << q << " = " << S[q] << ' ' << E[q] << endl;
for (int j = __lg(N); j >= 0; --j) {
if (~startTree.anc[j][S[q]] && startTree.anc[j][S[q]] >= L[q]) S[q] = startTree.anc[j][S[q]];
if (~finishTree.anc[j][E[q]] && finishTree.anc[j][E[q]] <= R[q]) E[q] = finishTree.anc[j][E[q]];
}
assert(S[q] >= L[q] && E[q] <= R[q]);
// cout << q << " = " << S[q] << ' ' << E[q] << endl;
queries[E[q]].emplace_back(S[q], q);
}
BIT bit(N);
vector<int> ans(Q, 0);
finishTree.solve(N - 1, bit, queries, ans, tin, tout);
// for (auto &x : ans) cout << "ans " << x << endl;
for (auto &x : ans) x = !!x;
return ans;
}
