#line 2 "ProCon/Library/template/util.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; constexpr i8 operator""_i8(unsigned long long n) noexcept { return static_cast(n); } constexpr i16 operator""_i16(unsigned long long n) noexcept { return static_cast(n); } constexpr i32 operator""_i32(unsigned long long n) noexcept { return static_cast(n); } constexpr i64 operator""_i64(unsigned long long n) noexcept { return static_cast(n); } constexpr u8 operator""_u8(unsigned long long n) noexcept { return static_cast(n); } constexpr u16 operator""_u16(unsigned long long n) noexcept { return static_cast(n); } constexpr u32 operator""_u32(unsigned long long n) noexcept { return static_cast(n); } constexpr u64 operator""_u64(unsigned long long n) noexcept { return static_cast(n); } constexpr char eoln = '\n'; template constexpr T infty = std::numeric_limits::max() / Div - 2; template using RevPriorityQueue = std::priority_queue, std::greater>; constexpr std::array, 4> dxy4 = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr std::array infty_list = {infty, infty, infty, infty, infty, infty}; template bool is_infty(const T v) { if (v > 0 and static_cast(v) > infty) return false; for (const auto e : infty_list) { if (e == static_cast(v)) return true; } return false; } class Range { struct Iterator { int itr; constexpr Iterator(const int pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iterator &other) const noexcept { return itr != other.itr; } constexpr int operator*() const noexcept { return itr; } }; const Iterator first, last; public: explicit constexpr Range(const int f, const int l) noexcept : first(f), last(std::max(f, l)) {} constexpr Iterator begin() const noexcept { return first; } constexpr Iterator end() const noexcept { return last; } }; class ReversedRange { struct Iterator { int itr; constexpr Iterator(const int pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { --itr; } constexpr bool operator!=(const Iterator &other) const noexcept { return itr != other.itr; } constexpr int operator*() const noexcept { return itr; } }; const Iterator first, last; public: explicit constexpr ReversedRange(const int f, const int l) noexcept : first(l - 1), last(std::min(f, l) - 1) {} constexpr Iterator begin() const noexcept { return first; } constexpr Iterator end() const noexcept { return last; } }; #define SIKICM_REP1(i, r) for (const int i : Range(0, r)) #define SIKICM_REP2(i, l, r) for (int i : Range(l, r)) #define SIKICM_RVP1(i, r) for (const int i : ReversedRange(0, r)) #define SIKICM_RVP2(i, l, r) for (int i : ReversedRange(l, r)) #define SIKICM_SELECT2(a, b, c, name, ...) name #define REP(...) SIKICM_SELECT2(__VA_ARGS__, SIKICM_REP2, SIKICM_REP1)(__VA_ARGS__) #define RVP(...) SIKICM_SELECT2(__VA_ARGS__, SIKICM_RVP2, SIKICM_RVP1)(__VA_ARGS__) #define HRL(n) for ([[maybe_unused]] const int loop_counter : Range(0, n)) template constexpr int len(const Container &c) { return static_cast(std::size(c)); } template constexpr bool chmin(T &v, const T a) { if (v > a) { v = a; return true; } return false; } template constexpr bool chmax(T &v, const T a) { if (v < a) { v = a; return true; } return false; } template constexpr T ceil_div(const T x, const T y) { assert(y != 0); assert(x >= 0 and y > 0); return (x + y - 1) / y; } template constexpr int lwb(const Container &c, const T &val) { return static_cast(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val))); } template constexpr int upb(const Container &c, const T &val) { return static_cast(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val))); } template constexpr int lmp(const Container &c, const F &f) { return static_cast( std::distance(c.cbegin(), std::partition_point(c.cbegin(), c.cend(), f))); } template auto make_vec(const int n, const T &value) { return std::vector(n, value); } template auto make_vec(const int n, Args... args) { return std::vector(n, make_vec(args...)); } template void renumber(const std::vector &order, std::vector &head, Tail &... tail) { const int n = len(order); std::vector sorted_head(n); REP(i, n) sorted_head[i] = head[order[i]]; head = std::move(sorted_head); if constexpr (sizeof...(Tail) != 0) { renumber(order, tail...); } } template std::vector priority_sort(std::vector &head, std::vector &... tail) { const int n = len(head); std::vector> res(n); REP(i, n) res[i] = std::make_tuple(head[i], tail[i]..., i); std::sort(res.begin(), res.end()); std::vector order(n); REP(i, 0, n) order[i] = std::get>>(res[i]); renumber(order, head, tail...); return order; } std::vector iotav(const int n) { std::vector ret(n); std::iota(ret.begin(), ret.end(), 0); return ret; } template auto calc_sum(const Container &c) { return std::accumulate(c.cbegin(), c.cend(), static_cast(0)); } template constexpr T ceil_log2(const T x) { int e = 0; while ((static_cast(1) << e) < x) ++e; return e; } template constexpr int ceil_pow2(const T x) { return 1 << ceil_log2(x); } #line 5 "ProCon/Library/template/debug.hpp" #include namespace DebugImpl { template struct is_specialize : std::false_type {}; template struct is_specialize::type> : std::true_type {}; template struct is_specialize::type> : std::true_type {}; template struct is_specialize::value, void>> : std::true_type {}; void dump(const char &t) { std::cerr << t; } void dump(const std::string &t) { std::cerr << t; } void dump(const bool &t) { std::cerr << (t ? "true" : "false"); } template ::value, std::nullptr_t> = nullptr> void dump(const U &t) { std::cerr << t; } template void dump(const T &t, std::enable_if_t::value> * = nullptr) { std::string res; if (is_infty(t)) res = "inf"; if constexpr (std::is_signed::value) { if (is_infty(-t)) res = "-inf"; } if (res.empty()) res = std::to_string(t); std::cerr << res; } template void dump(const std::pair &); template void dump(const std::pair &); template void dump(const T &t, std::enable_if_t::value> * = nullptr) { std::cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); std::cerr << (++it == t.end() ? "" : ", "); } std::cerr << " ]"; } template void dump(const std::pair &t) { std::cerr << "( "; dump(t.first); std::cerr << ", "; dump(t.second); std::cerr << " )"; } template void dump(const std::pair &t) { std::cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); std::cerr << (i == t.second - 1 ? "" : ", "); } std::cerr << " ]"; } void trace() { std::cerr << std::endl; } template void trace(Head &&head, Tail &&... tail) { std::cerr << " "; dump(head); if (sizeof...(tail) != 0) std::cerr << ','; trace(std::forward(tail)...); } } // namespace DebugImpl #ifdef SIKI_DEBUG #define vpr(...) \ do { \ std::cerr << "## " << #__VA_ARGS__ << " ="; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define vpr(...) (void(0)) #endif // https://github.com/NyaanNyaan/library/blob/master/template/debug.hpp #line 2 "ProCon/Library/template/macro.hpp" #define ALL(x) (x).begin(), (x).end() #define pf push_front #define pb push_back #define ef emplace_front #define eb emplace_back #define ppf pop_front #define ppb pop_back #line 4 "main.cpp" #include using namespace std; int main() { int N; cin >> N; vector U(N - 1), V(N - 1); vector> Tree(N); REP(i, N - 1) { cin >> U[i] >> V[i]; --U[i], --V[i]; Tree[U[i]].pb(V[i]); Tree[V[i]].pb(U[i]); } vector> chd_ds(N); { auto dfs = [&](auto &&self, const int v, const int p) -> int { for (const int t : Tree[v]) { if (t == p) { chd_ds[v].pb(0); continue; } const int chd_s = self(self, t, v); chd_ds[v].pb(chd_s); } return *max_element(ALL(chd_ds[v])) + 1; }; dfs(dfs, 0, -1); } vpr(chd_ds); vector subtree_dim(N); { auto dfs = [&](auto &&self, const int v, const int p) -> void { int ret = 0; for (const int t : Tree[v]) { if (t == p) continue; self(self, t, v); chmax(ret, subtree_dim[t]); } auto calc_subtree_dim1 = [&]() { int ma = 0, ma_id = 0; REP(i, len(Tree[v])) if (chmax(ma, chd_ds[v][i])) ma_id = i; int sm = 0; REP(i, len(Tree[v])) if (i != ma_id) chmax(sm, chd_ds[v][i]); return ma + sm; }; subtree_dim[v] = max(ret, calc_subtree_dim1()); }; dfs(dfs, 0, -1); } vpr(subtree_dim); int ans = subtree_dim[0]; auto dfs_reroot = [&](auto &&self, const int v, const int p, const int p_max_depth, const int p_dim) -> void { if (len(Tree[v]) == 1 and v != 0) { chmin(ans, max(p_dim, ceil_div(p_dim, 2) + 1)); return; } if (v != 0) chmin(ans, max({subtree_dim[v], p_dim, ceil_div(subtree_dim[v], 2) + ceil_div(p_dim, 2) + 1})); vector ma1_l, ma2_l, ma1_r, ma2_r; auto make_tb = [&](vector &m1, vector &m2) { m1.pb(0); m2.pb(0); for (const int e : chd_ds[v]) { if (m1.back() <= e) { m2.pb(m1.back()); m1.pb(e); } else if (m2.back() < e) { m1.pb(m1.back()); m2.pb(e); } else { m1.pb(m1.back()); m2.pb(m2.back()); } } }; make_tb(ma1_l, ma2_l); reverse(ALL(chd_ds[v])); make_tb(ma1_r, ma2_r); reverse(ALL(chd_ds[v])); reverse(ALL(ma1_r)); reverse(ALL(ma2_r)); vector mal2, mar2; mal2.pb(0); REP(i, len(Tree[v])) { const int t = Tree[v][i]; if (t == p) { mal2.pb(mal2.back()); continue; } mal2.pb(max(mal2.back(), subtree_dim[t])); } mar2.pb(0); RVP(i, len(Tree[v])) { const int t = Tree[v][i]; if (t == p) { mar2.pb(mar2.back()); continue; } mar2.pb(max(mar2.back(), subtree_dim[t])); } reverse(ALL(mar2)); vpr(mal2);vpr(mar2); REP(i, len(Tree[v])) { const int t = Tree[v][i]; if (t == p) continue; int v1 = max(ma1_l[i], ma1_r[i + 1]); int v2 = max(min(ma1_l[i], ma1_r[i + 1]), max(ma2_l[i], ma2_r[i + 1])); int n_dim = v1 + v2 + p_max_depth + 1 - min({v1, v2, p_max_depth + 1}); chmax(n_dim, p_dim); chmax(n_dim, max(mal2[i], mar2[i + 1])); int n_mad = max(p_max_depth + 1, max(ma1_l[i], ma1_r[i + 1])); self(self, t, v, n_mad, n_dim); } }; dfs_reroot(dfs_reroot, 0, -1, -1, 0); cout << ans << endl; }