0fceacab598431102d1fabf7800b96c7f6ff0213cbc320066918f321829a4a37
// https://szkopul.edu.pl/problemset/problem/sKmyIHBMNi9EV3WO6GQ4xoFt/site/?key=statement
// 0.04 s
#pragma GCC optimize("O3,unroll-loops,omit-frame-pointer,inline")
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
constexpr int MAXN = 200'005;
constexpr int INF = 0x3f3f3f3f;
char* in_ptr;
inline void init_io() {
struct stat sb;
fstat(0, &sb);
in_ptr = static_cast<char*>(mmap(nullptr, sb.st_size, PROT_READ, MAP_PRIVATE, 0, 0));
}
inline int next_int() {
while (*in_ptr <= ' ')
++in_ptr;
int res = *in_ptr++ - '0';
while (*in_ptr >= '0') {
res = res * 10 + (*in_ptr++ - '0');
}
return res;
}
inline void print_int(int x) {
char s[32];
int idx = 30;
s[31] = '\n';
if (x == 0) {
s[idx--] = '0';
} else {
while (x > 0) {
s[idx--] = (char)('0' + (x % 10));
x /= 10;
}
}
write(1, &s[idx + 1], 31 - idx);
}
struct alignas(64) DpNode {
int v[11];
uint16_t mask;
int pad[3];
inline void init_leaf() {
memset(v, 0x3f, sizeof(v));
v[2] = 0;
mask = (1U << 2);
}
};
DpNode dp[MAXN];
struct Res27 {
int v[27];
uint32_t mask;
};
struct MergeTableDense {
uint8_t t[27][11];
constexpr MergeTableDense() : t{} {
for (int r = 0; r < 27; ++r) {
int x = r / 9, y = (r / 3) % 3, z = r % 3;
for (int d = 0; d < 11; ++d) {
int a = 0, b = 0, c = 0;
if (d < 9) {
a = 0;
b = d / 3;
c = d % 3;
} else if (d == 9) {
a = 1;
b = 0;
c = 0;
} else {
a = 2;
b = 0;
c = 0;
}
int q = (x + a < 2) ? (x + a) : 2;
int w = (y > b) ? y : b;
int d1 = z - a;
int d2 = c - x;
int max_d = (d1 > d2) ? d1 : d2;
int e = (max_d > 0) ? max_d : 0;
t[r][d] = static_cast<uint8_t>(q * 9 + w * 3 + e);
}
}
}
};
constexpr MergeTableDense merge_tbl{};
struct RawEdge {
int u, v;
};
RawEdge raw_edges[MAXN];
int deg[MAXN], head[MAXN], to[MAXN * 2];
int child_cnt[MAXN], parent_node[MAXN];
int order[MAXN];
inline void solve_single_child(DpNode& __restrict__ u, const DpNode& __restrict__ c) {
const int* __restrict__ cv = c.v;
int* __restrict__ uv = u.v;
uv[0] = cv[10];
uv[1] = cv[9];
uv[2] = cv[0];
uv[3] = INF;
uv[4] = INF;
uv[5] = cv[1];
uv[6] = INF;
uv[7] = INF;
uv[8] = cv[2];
int m01 = std::min(cv[0], cv[1]);
int m23 = std::min(cv[2], cv[3]);
int m45 = std::min(cv[4], cv[5]);
int m910 = std::min(cv[9], cv[10]);
int m_y1 = std::min(std::min(m01, m23), std::min(m45, m910));
int m67 = std::min(cv[6], cv[7]);
int m_all = std::min(m_y1, std::min(m67, cv[8]));
uv[9] = m_y1 + 1;
uv[10] = m_all + 2;
uint32_t cm = c.mask;
uint32_t m = ((cm >> 10) & 1) | (((cm >> 9) & 1) << 1) | ((cm & 1) << 2) | (((cm >> 1) & 1) << 5) | (((cm >> 2) & 1) << 8);
if (cm & 0x63f) m |= (1U << 9);
if (cm) m |= (1U << 10);
u.mask = static_cast<uint16_t>(m);
}
inline void init_res_from_child(Res27& __restrict__ res, const DpNode& __restrict__ c) {
memset(res.v, 0x3f, sizeof(res.v));
uint32_t cm = c.mask;
uint32_t rm = 0;
while (cm) {
int idx = __builtin_ctz(cm);
cm &= cm - 1;
int val = c.v[idx];
int r_idx = (idx < 9) ? idx : (idx == 9 ? 9 : 18);
res.v[r_idx] = val;
rm |= (1U << r_idx);
}
res.mask = rm;
}
inline void merge_nodes(Res27& __restrict__ res, const DpNode& __restrict__ child) {
int nowy_v[27];
memset(nowy_v, 0x3f, sizeof(nowy_v));
uint32_t nowy_mask = 0;
uint8_t c_indices[11];
int c_vals[11];
int c_sz = 0;
uint32_t cm = child.mask;
while (cm) {
int idx = __builtin_ctz(cm);
cm &= cm - 1;
c_indices[c_sz] = static_cast<uint8_t>(idx);
c_vals[c_sz] = child.v[idx];
c_sz++;
}
uint32_t rm = res.mask;
if (c_sz == 1) {
uint8_t c0 = c_indices[0];
int v0 = c_vals[0];
while (rm) {
int r_idx = __builtin_ctz(rm);
rm &= rm - 1;
int out_idx = merge_tbl.t[r_idx][c0];
int cand = res.v[r_idx] + v0;
if (cand < nowy_v[out_idx]) {
nowy_v[out_idx] = cand;
nowy_mask |= (1U << out_idx);
}
}
} else {
while (rm) {
int r_idx = __builtin_ctz(rm);
rm &= rm - 1;
int r_val = res.v[r_idx];
const uint8_t* __restrict__ tr = merge_tbl.t[r_idx];
for (int j = 0; j < c_sz; ++j) {
int out_idx = tr[c_indices[j]];
int cand = r_val + c_vals[j];
if (cand < nowy_v[out_idx]) {
nowy_v[out_idx] = cand;
nowy_mask |= (1U << out_idx);
}
}
}
}
memcpy(res.v, nowy_v, sizeof(nowy_v));
res.mask = nowy_mask;
}
inline void par_multi(const Res27& __restrict__ res, DpNode& __restrict__ u) {
int* __restrict__ uv = u.v;
int m_all = INF, m_y1 = INF;
uint32_t rm = res.mask;
while (rm) {
int idx = __builtin_ctz(rm);
rm &= rm - 1;
int val = res.v[idx];
if (val < m_all) m_all = val;
int y = (idx / 3) % 3;
if (y <= 1 && val < m_y1) m_y1 = val;
}
uv[0] = res.v[18];
uv[1] = res.v[9];
uv[2] = res.v[0];
uv[3] = res.v[19];
uv[4] = res.v[10];
uv[5] = res.v[1];
uv[6] = res.v[20];
uv[7] = res.v[11];
uv[8] = res.v[2];
uv[9] = m_y1 + 1;
uv[10] = m_all + 2;
uint32_t m = 0;
for (int i = 0; i < 11; ++i) {
if (uv[i] < INF) m |= (1U << i);
}
u.mask = static_cast<uint16_t>(m);
}
int main() {
init_io();
int n = next_int();
if (n <= 1) {
print_int(0);
_exit(0);
}
for (int i = 0; i < n - 1; ++i) {
int u = next_int();
int v = next_int();
raw_edges[i] = {u, v};
deg[u]++;
deg[v]++;
}
head[1] = 0;
for (int i = 1; i <= n; ++i) {
head[i + 1] = head[i] + deg[i];
deg[i] = 0;
}
for (int i = 0; i < n - 1; ++i) {
int u = raw_edges[i].u;
int v = raw_edges[i].v;
to[head[u] + deg[u]++] = v;
to[head[v] + deg[v]++] = u;
}
int q_head = 0, q_tail = 0;
order[q_tail++] = 1;
parent_node[1] = 0;
while (q_head < q_tail) {
int u = order[q_head++];
int p = parent_node[u];
int w = head[u];
int end_e = head[u + 1];
for (int e = head[u]; e < end_e; ++e) {
int v = to[e];
if (v != p) {
parent_node[v] = u;
to[w++] = v;
order[q_tail++] = v;
}
}
child_cnt[u] = w - head[u];
}
for (int i = n - 1; i >= 0; --i) {
int u = order[i];
int k = child_cnt[u];
int* ch = &to[head[u]];
if (k == 0) {
dp[u].init_leaf();
} else if (k == 1) {
solve_single_child(dp[u], dp[ch[0]]);
} else {
Res27 res;
init_res_from_child(res, dp[ch[0]]);
for (int j = 1; j < k; ++j) {
merge_nodes(res, dp[ch[j]]);
}
par_multi(res, dp[u]);
}
}
int ans = std::min({dp[1].v[0], dp[1].v[1], dp[1].v[2], dp[1].v[9], dp[1].v[10]});
print_int(ans);
_exit(0);
}