#include <bits/stdc++.h>
#include "collapse.h"
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
class rep {
struct Iter {
usize itr;
constexpr Iter(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
constexpr usize operator*() const noexcept { return itr; }
};
const Iter first, last;
public:
explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
class RollbackUnionFind {
std::vector<usize> data;
std::stack<std::pair<usize, usize>> history;
public:
explicit RollbackUnionFind(const usize size = 0) : data(size, -1), history() {}
usize size() const { return data.size(); }
usize leader(usize u) const {
assert(u < size());
while (data[u] < size()) u = data[u];
return u;
}
usize size(const usize u) const {
assert(u < size());
return -data[leader(u)];
}
std::pair<usize, bool> merge(usize u, usize v) {
assert(u < size());
assert(v < size());
u = leader(u);
v = leader(v);
if (u == v) return std::make_pair(u, false);
if (data[u] > data[v]) std::swap(u, v);
history.emplace(u, data[u]);
history.emplace(v, data[v]);
data[u] += data[v];
data[v] = u;
return std::make_pair(u, true);
}
bool same(const usize u, const usize v) const {
assert(u < size());
assert(v < size());
return leader(u) == leader(v);
}
void rollback(const usize steps) {
assert(2 * steps <= history.size());
for (usize i = 2 * steps; i > 0; --i) {
const auto [k, x] = history.top();
history.pop();
data[k] = x;
}
}
};
template <class T> using Vec = std::vector<T>;
constexpr usize BSIZE = 400;
Vec<int> calc(const usize N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
const auto C = T.size();
const auto Q = W.size();
Vec<std::pair<int, int>> edge;
edge.reserve(C);
for (const auto i : rep(0, C)) {
if (X[i] > Y[i]) {
std::swap(X[i], Y[i]);
}
edge.emplace_back(Y[i], X[i]);
}
std::sort(edge.begin(), edge.end());
edge.erase(std::unique(edge.begin(), edge.end()), edge.end());
Vec<usize> eid(C);
for (const auto i : rep(0, C)) {
eid[i] = std::lower_bound(edge.begin(), edge.end(), std::make_pair(Y[i], X[i])) - edge.begin();
}
const auto Blocks = (C + BSIZE - 1) / BSIZE;
Vec<Vec<usize>> qid(Blocks);
for (const auto i : rep(0, Q)) {
qid[W[i] / BSIZE].push_back(i);
}
Vec<int> ret(Q);
for (const auto block : rep(0, Blocks)) {
const auto low = BSIZE * block;
const auto high = std::min(C, low + BSIZE);
auto& qs = qid[block];
std::sort(qs.begin(), qs.end(), [&](const usize i, const usize j) { return P[i] < P[j]; });
Vec<char> usage(edge.size()), changes(edge.size());
for (const auto i : rep(0, low)) {
usage[eid[i]] ^= 1;
}
for (const auto i : rep(low, high)) {
changes[eid[i]] = true;
}
Vec<usize> naive;
for (const auto i : rep(0, edge.size())) {
if (changes[i]) {
naive.push_back(i);
}
}
RollbackUnionFind dsu(N);
usize comps = N, seen = 0;
for (const auto i : qs) {
while (seen < edge.size() and edge[seen].first <= P[i]) {
if (!changes[seen] and usage[seen]) {
comps -= dsu.merge(edge[seen].first, edge[seen].second).second;
}
seen += 1;
}
const auto memo = comps;
for (const auto j : rep(low, W[i] + 1)) {
usage[eid[j]] ^= 1;
}
for (const auto e : naive) {
if (usage[e] and edge[e].first <= P[i]) {
comps -= dsu.merge(edge[e].first, edge[e].second).second;
}
}
for (const auto j : rep(low, W[i] + 1)) {
usage[eid[j]] ^= 1;
}
ret[i] = comps;
dsu.rollback(memo - comps);
comps = memo;
}
}
return ret;
}
Vec<int> simulateCollapse(int N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
const auto C = T.size();
const auto Q = W.size();
auto ret = calc(N, T, X, Y, W, P);
for (const auto i : rep(0, C)) {
X[i] = N - X[i] - 1;
Y[i] = N - Y[i] - 1;
}
for (const auto i : rep(0, Q)) {
P[i] = N - P[i] - 2;
}
const auto tmp = calc(N, T, X, Y, W, P);
for (const auto i : rep(0, Q)) {
ret[i] += tmp[i];
ret[i] -= N;
}
return ret;
}
