#include #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, std::vector> edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i targets, std::vector bounds){ AdjacencyList res; res.mn = bounds.size() - 1; res.E = std::move(targets); res.I = std::move(bounds); return res; } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Edge& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyListEdgeIndexed(int n, const std::vector>& edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = { v, i }; if(rev) E[--buf[v]] = { u, i }; } I = std::move(buf); } AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {} AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyListEdgeIndexed reversed_edges() const { AdjacencyListEdgeIndexed res; int n = res.mn = mn; std::vector buf(n+1, 0); for(auto [v,i] : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u struct S { int height; int diam; }; struct Edge { }; S rake(S l, S r){ S res; res.height = std::max(l.height, r.height); res.diam = std::max({ l.diam, r.diam, l.height + r.height }); return res; } S compress(S l, Edge edge){ S res; res.height = l.height + 1; res.diam = std::max(l.diam, res.height); return res; } S e(){ return { 0,0 }; } S node(int v){ return { 0,0 }; } struct AnyDirectionTreeDP{ std::vector low; std::vector high; std::vector edgei; AnyDirectionTreeDP(const nachia::AdjacencyListEdgeIndexed& adj){ int n = adj.num_vertices(); std::vector bfs = {0}; bfs.reserve(n); std::vector P(n, -1); edgei.assign(n, -1); for(int i=0; i=1; i--){ int p = bfs[i]; if(edgei[P[p]] == -1) continue; low[edgei[P[p]]] = rake(low[edgei[P[p]]], compress(low[edgei[p]], {})); } for(int i=0; i=0; ci--) if(P[p] != adj[p][ci].to){ int c = adj[p][ci].edgeidx; high[c] = rake(high[c], fold); fold = rake(fold, compress(low[c], {})); } fold = e(); for(int ci=0; ci #include #include using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using modint = atcoder::static_modint<1000000007>; int main(){ int N; cin >> N; vector> edges(N-1); rep(i,N-1){ int u,v; cin >> u >> v; u--; v--; edges[i] = make_pair(u,v); } auto adj = nachia::AdjacencyListEdgeIndexed(N, edges, true); auto treedp = AnyDirectionTreeDP(adj); int ans = N; rep(i,N-1){ int diam1 = treedp.high[i].diam; int diam2 = treedp.low[i].diam; int cr_ans = (diam1 + 1) / 2 + (diam2 + 1) / 2 + 1; cr_ans = max({ cr_ans, diam1, diam2 }); ans = min(ans, cr_ans); } cout << ans << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;