#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> Tree(N); HRL(N - 1) { int x, y; cin >> x >> y; --x, --y; Tree[x].pb(y); Tree[y].pb(x); } auto merge = [](multiset &a, multiset &&b) { if (len(a) < len(b)) swap(a, b); for (const int e : b) a.insert(e); }; auto dfs2 = [&](auto &&self, const int v, const int p) -> multiset { multiset res; for (const int t : Tree[v]) { if (t == p) continue; merge(res, self(self, t, v)); } int a = 0; HRL(min(2, len(res))) { a += *res.rbegin(); res.erase(--res.end()); } res.insert(a + 1); return res; }; cout << *dfs2(dfs2, 0, -1).rbegin() << eoln; }