#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include "werewolf.h"
#include <cassert>
#include <functional>
template<typename Type>
class FenwickTree {
private:
std::vector<Type> bit;
public:
FenwickTree(int size = 0, Type val = 0) {
Assign(size, val);
}
void Assign(int size = 0, Type val = 0) {
bit.assign(size+1, 0);
if (size&&val) {
for (int i = 1; i < bit.size(); i++) {
bit[i] += val;
if (i+(i&-i)<bit.size()) {
bit[i+(i&-i)] += bit[i];
}
}
}
}
void Add(int pos, Type val) {
while (pos < bit.size()) {
bit[pos] += val;
pos += pos&-pos;
}
}
Type Query(int pos) {
Type ret = 0;
while (pos > 0) {
ret += bit[pos];
pos ^= pos&-pos;
}
return ret;
}
Type Query(int l, int r) {
return Query(r) - Query(l-1);
}
};
class DSU {
private:
std::vector<int> t;
std::vector<int> sz;
public:
DSU(int n = 0) {
t.assign(n, 0); std::iota(t.begin(),t.end(),0);
sz.assign(n, 1);
}
int Find(int k) {
if (t[k]!=k) return t[k] = Find(t[k]);
return t[k];
}
int Unite(int a, int b) {
a = Find(a);
b = Find(b);
if (a==b) {
return 0;
}
if (sz[a]<sz[b]) {
std::swap(a,b);
}
sz[a] += sz[b];
t[b] = a;
return 1;
}
int UniteExplicit(int a, int b) {
a = Find(a);
b = Find(b);
if (a==b) {
return 0;
}
sz[a] += sz[b];
t[b] = a;
return 1;
}
};
struct Query {
int l, r, pfx, idx, sgn;
Query():
l(0), r(0), pfx(0), idx(0), sgn(0) {}
Query(int l, int r, int pfx, int idx, int sgn):
l(l), r(r), pfx(pfx), idx(idx), sgn(sgn) {}
};
int gs, q;
std::vector<std::vector<int>> adj_list;
std::vector<std::vector<int>> krt_less;
std::vector<int> krt_less_tour;
int krt_less_label[400005];
int krt_less_tin[400005];
int krt_less_tout[400005];
int krt_less_depth[400005];
int krt_less_up[18][400005];
std::vector<std::vector<int>> krt_greater;
std::vector<int> krt_greater_tour;
int krt_greater_label[400005];
int krt_greater_tin[400005];
int krt_greater_tout[400005];
int krt_greater_depth[400005];
int krt_greater_up[18][400005];
void build_krts() {
// less
std::vector<bool> active(gs+1, 0);
DSU dsu(2*gs+5);
for (int i = 0, timer = gs; i < gs; i++) {
active[i] = 1;
for (const auto& j : adj_list[i]) {
if (active[j]) {
int ri = dsu.Find(i);
int rj = dsu.Find(j);
if (ri!=rj) {
dsu.UniteExplicit(timer, ri);
dsu.UniteExplicit(timer, rj);
krt_less[timer].emplace_back(ri);
krt_less[timer].emplace_back(rj);
krt_less_label[timer] = i;
//std::cout << timer << " " << krt_less_label[timer] << " " << ri << "\n";
//std::cout << timer << " " << krt_less_label[timer] << " " << rj << "\n";
++timer;
}
}
}
}
// greater
active.assign(gs+1, 0);
dsu = DSU(2*gs+5);
for (int i = gs-1, timer = gs; i >= 0; i--) {
active[i] = 1;
for (const auto& j : adj_list[i]) {
if (active[j]) {
int ri = dsu.Find(i);
int rj = dsu.Find(j);
if (ri!=rj) {
//std::cout << timer << " " << ri << "\n";
//std::cout << timer << " " << rj << "\n";
dsu.UniteExplicit(timer, ri);
dsu.UniteExplicit(timer, rj);
krt_greater[timer].emplace_back(ri);
krt_greater[timer].emplace_back(rj);
krt_greater_label[timer] = i;
//std::cout << timer << " " << krt_greater_label[timer] << " " << ri << "\n";
//std::cout << timer << " " << krt_greater_label[timer] << " " << rj << "\n";
++timer;
}
}
}
}
}
void process_krts() {
const std::function<void(int, std::vector<std::vector<int>>&, std::vector<int>&, int*, int*, int*, int[18][400005])>
dfs = [&](int k, std::vector<std::vector<int>>& adj, std::vector<int>& tour, int* tin, int* tout, int* depth, int up[18][400005]) {
//std::cout << k << "\n";
tour.emplace_back(k);
tin[k] = tour.size()-1;
for (const auto& i : adj[k]) {
depth[i] = depth[k]+1;
up[0][i] = k;
for (int j = 1; j < 18; j++) {
up[j][i] = up[j-1][up[j-1][i]];
}
dfs(i, adj, tour, tin, tout, depth, up);
}
tout[k] = tour.size()-1;
};
dfs(2*gs-2, krt_less, krt_less_tour, krt_less_tin, krt_less_tout, krt_less_depth, krt_less_up);
dfs(2*gs-2, krt_greater, krt_greater_tour, krt_greater_tin, krt_greater_tout, krt_greater_depth, krt_greater_up);
}
int root_search_less(int node, int tgt) {
for (int step = 17; step >= 0; step--) {
if ((1<<step) <= krt_less_depth[node] && krt_less_label[krt_less_up[step][node]] <= tgt) {
node = krt_less_up[step][node];
}
}
return node;
}
int root_search_greater(int node, int tgt) {
for (int step = 17; step >= 0; step--) {
if ((1<<step) <= krt_greater_depth[node] && krt_greater_label[krt_greater_up[step][node]] >= tgt) {
node = krt_greater_up[step][node];
}
}
return node;
}
std::vector<int> solve_queries(std::vector<Query> queries) {
std::sort(queries.begin(),queries.end(),[](const Query& a, const Query& b) {
return a.pfx < b.pfx;
});
std::vector<int> ret(q, 0);
std::vector<int> pos(2*gs+5, -1);
for (int i = 0; i < krt_greater_tour.size()-1; i++) {
if (krt_greater_tour[i] < gs) {
pos[krt_greater_tour[i]] = i;
}
}
int scanline = 0;
FenwickTree<int> fnwk(2*gs+5, 0);
for (const auto& [ql, qr, qpfx, qidx, qsgn] : queries) {
while (scanline <= qpfx) {
if (pos[krt_less_tour[scanline]]!=-1 && krt_less_tour[scanline] < gs) {
//std::cout << scanline << " " << pos[krt_less_tour[scanline]] << "\n";
fnwk.Add(pos[krt_less_tour[scanline]]+1, 1);
}
++scanline;
}
//std::cout << ql << " " << qr << " " << qpfx << " " << qidx << " " << qsgn << " " << fnwk.Query(ql+1,qr+1) << "\n";
ret[qidx] += qsgn * fnwk.Query(ql+1, qr+1);
}
return ret;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
gs = N;
q = S.size();
adj_list.resize(gs+1);
krt_less.resize(2*gs+5);
krt_greater.resize(2*gs+5);
for (int i = 0; i < gs-1; i++) {
adj_list[X[i]].emplace_back(Y[i]);
adj_list[Y[i]].emplace_back(X[i]);
}
build_krts();
process_krts();
/*for (const auto& i : krt_less_tour) {
std::cout << i << " ";
}
std::cout << "\n";
for (int i = 0; i < 2*gs-1; i++) {
std::cout << krt_less_tin[i] << " " << krt_less_tout[i] << "\n";
}*/
/*for (const auto& i : krt_less_tour) {
std::cout << i << " ";
}
std::cout << "\n";*/
std::vector<Query> queries;
for (int i = 0; i < S.size(); i++) {
int root_human = root_search_greater(S[i], L[i]);
int root_wolf = root_search_less(E[i], R[i]);
int l1 = krt_greater_tin[root_human], r1 = krt_greater_tout[root_human];
int l2 = krt_less_tin[root_wolf], r2 = krt_less_tout[root_wolf];
/*if (l1 == r1 && krt_greater_tour[l1] < gs) {
continue;
}
if (l2 == r2 && krt_less_tour[l2] < gs) {
continue;
}*/
queries.emplace_back(l1,r1,r2,i,1);
if (l2-1>=0) {
queries.emplace_back(l1,r1,l2-1,i,-1);
}
//std::cout << root_human << " " << root_wolf << "\n";
//std::cout << l1 << " " << r1 << " " << l2 << " " << r2 << "\n";
}
std::vector<int> ret = solve_queries(queries);
for (int i = 0; i < ret.size(); i++) {
ret[i] = !!ret[i];
}
return ret;
}
