#include <bits/stdc++.h>
#include "catdog.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; }
};
template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div;
template <class T> bool setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class F> struct RecursiveLambda : private F {
explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class F> constexpr decltype(auto) rec_lambda(F&& f) {
using G = std::decay_t<F>;
return RecursiveLambda<G>(std::forward<G>(f));
}
class HeavyLightDecomposition {
struct Node {
std::vector<usize> adjacent;
usize parent, subtree, head, enter, exit;
Node() = default;
};
std::vector<Node> node;
public:
HeavyLightDecomposition() = default;
explicit HeavyLightDecomposition(const std::vector<std::vector<usize>>& tree, const usize root = 0)
: HeavyLightDecomposition(tree, std::vector<usize>({root})) {}
explicit HeavyLightDecomposition(const std::vector<std::vector<usize>>& forest, const std::vector<usize>& root)
: node(forest.size()) {
for (const auto i : rep(0, size())) node[i].adjacent = forest[i];
const auto setup = rec_lambda([&](auto&& dfs, const usize u, const usize p) -> void {
node[u].parent = p;
node[u].subtree = 1;
for (const auto v : node[u].adjacent) {
if (v != p) {
dfs(v, u);
node[u].subtree += node[v].subtree;
}
}
});
for (const auto r : root) setup(r, r);
usize time = 0;
const auto decompose = rec_lambda([&](auto&& dfs, const usize u, const usize h) -> void {
node[u].head = h;
node[u].enter = time;
time += 1;
usize select = size();
for (const auto v : node[u].adjacent) {
if (v != node[u].parent and (select == size() or node[select].subtree < node[v].subtree)) {
select = v;
}
}
if (select != size()) {
dfs(select, h);
for (const auto v : node[u].adjacent) {
if (v != node[u].parent and v != select) {
dfs(v, v);
}
}
}
node[u].exit = time;
});
for (const auto r : root) decompose(r, r);
}
usize size() const { return node.size(); }
const Node& info(const usize u) const {
assert(u < size());
return node[u];
}
usize lca(usize u, usize v) const {
assert(u < size());
assert(v < size());
if (node[u].enter > node[v].enter) std::swap(u, v);
while (node[u].enter < node[v].enter) {
if (node[u].head == node[v].head) return u;
v = node[node[v].head].parent;
}
return v;
}
std::vector<std::pair<usize, usize>> path(usize u, usize p) const {
assert(u < size());
assert(p < size());
assert(node[p].enter <= node[u].enter and node[u].exit <= node[p].exit);
std::vector<std::pair<usize, usize>> ret;
while (node[u].head != node[p].head) {
ret.emplace_back(u, node[u].head);
u = node[node[u].head].parent;
}
ret.emplace_back(u, p);
return ret;
}
};
class revrep {
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 revrep(const usize first, const usize last) noexcept
: first(last - 1), last(std::min(first, last) - 1) {}
constexpr Iter begin() const noexcept { return first; }
constexpr Iter end() const noexcept { return last; }
};
constexpr u64 ceil_log2(const u64 x) {
u64 e = 0;
while (((u64)1 << e) < x) ++e;
return e;
}
template <class Monoid> class SegmentTree {
using M = Monoid;
usize internal_size, seg_size;
std::vector<M> data;
void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; }
public:
explicit SegmentTree(const usize size = 0, const M& value = M::zero()) : SegmentTree(std::vector<M>(size, value)) {}
explicit SegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) {
seg_size = 1 << ceil_log2(internal_size);
data = std::vector<M>(2 * seg_size, M::zero());
for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i];
for (const usize i : revrep(1, seg_size)) fetch(i);
}
usize size() const { return internal_size; }
void assign(usize i, const M& value) {
assert(i < internal_size);
i += seg_size;
data[i] = value;
while (i > 1) {
i >>= 1;
fetch(i);
}
}
M fold() const { return data[1]; }
M fold(usize l, usize r) const {
assert(l <= r and r <= internal_size);
l += seg_size;
r += seg_size;
M ret_l = M::zero(), ret_r = M::zero();
while (l < r) {
if (l & 1) ret_l = ret_l + data[l++];
if (r & 1) ret_r = data[--r] + ret_r;
l >>= 1;
r >>= 1;
}
return ret_l + ret_r;
}
template <class F> usize max_right(usize l, const F& f) const {
assert(l <= internal_size);
assert(f(M::zero()));
if (l == internal_size) return internal_size;
l += seg_size;
M sum = M::zero();
do {
while (!(l & 1)) l >>= 1;
if (!f(sum + data[l])) {
while (l < seg_size) {
l = 2 * l;
if (f(sum + data[l])) sum = sum + data[l++];
}
return l - seg_size;
}
sum = sum + data[l++];
} while ((l & -l) != l);
return internal_size;
}
template <class F> usize min_left(usize r, const F& f) const {
assert(r <= internal_size);
assert(f(M::zero()));
if (r == 0) return 0;
r += seg_size;
M sum = M::zero();
do {
r -= 1;
while (r > 1 and (r & 1)) r >>= 1;
if (!f(data[r] + sum)) {
while (r < seg_size) {
r = 2 * r + 1;
if (f(data[r] + sum)) sum = data[r--] + sum;
}
return r + 1 - seg_size;
}
sum = data[r] + sum;
} while ((r & -r) != r);
return 0;
}
};
template <class T> using Vec = std::vector<T>;
namespace catdog {
constexpr usize MAX = INFTY<usize, 3>;
struct Monoid {
std::array<std::array<usize, 2>, 2> cost;
static constexpr Monoid zero() { return Monoid{{0, MAX, MAX, 0}}; }
Monoid operator+(const Monoid& other) const {
std::array<std::array<usize, 2>, 2> ret{};
ret[0][0] = ret[0][1] = ret[1][0] = ret[1][1] = MAX;
for (const auto i : rep(0, 2))
for (const auto j : rep(0, 2))
for (const auto k : rep(0, 2))
for (const auto l : rep(0, 2)) setmin(ret[i][l], cost[i][j] + other.cost[k][l] + (j ^ k));
return Monoid{ret};
}
};
usize N;
HeavyLightDecomposition hld;
Vec<usize> bad, len;
Vec<std::array<usize, 2>> sum;
SegmentTree<Monoid> seg;
void init(const Vec<Vec<usize>>& graph) {
N = graph.size();
hld = HeavyLightDecomposition(graph);
bad = Vec<usize>(N, 2);
len = Vec<usize>(N, 0);
for (const auto u : rep(0, N)) {
len[hld.info(u).head] += 1;
}
sum = Vec<std::array<usize, 2>>(N);
seg = SegmentTree<Monoid>(N);
}
std::array<usize, 2> get(const Monoid& m) {
return {std::min(m.cost[0][0], m.cost[0][1]), std::min(m.cost[1][0], m.cost[1][1])};
}
usize set(usize u, const usize k) {
u -= 1;
bad[u] = k;
while (true) {
const auto h = hld.info(u).head;
const auto cur = get(seg.fold(hld.info(h).enter, hld.info(h).enter + len[h]));
{
std::array<std::array<usize, 2>, 2> arr;
for (const auto i : rep(0, 2)) {
arr[i].fill(MAX);
if (i != bad[u]) {
arr[i][i] = sum[u][i];
}
}
seg.assign(hld.info(u).enter, Monoid{arr});
}
const auto next = get(seg.fold(hld.info(h).enter, hld.info(h).enter + len[h]));
const auto p = hld.info(h).parent;
if (p == h) {
return std::min(next[0], next[1]);
}
for (const auto i : rep(0, 2)) {
sum[p][i] -= cur[i];
sum[p][i] += next[i];
}
u = p;
}
assert(false);
return 0;
}
}; // namespace catdog
void initialize(int N, Vec<int> A, Vec<int> B) {
Vec<Vec<usize>> graph(N);
for (const auto i : rep(0, N - 1)) {
A[i] -= 1;
B[i] -= 1;
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
catdog::init(graph);
}
int cat(int v) { return catdog::set(v, 0); }
int dog(int v) { return catdog::set(v, 1); }
int neighbor(int v) { return catdog::set(v, 2); }
