#pragma region my_template #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using pi = pair; using pl = pair; using ti = tuple; using tl = tuple; using vi = vector; using vpi = vector; using vti = vector; using vvi = vector; using usi = unordered_set; using vl = vector; using vpl = vector; using vtl = vector; using vvl = vector; using usl = unordered_set; #define range(i, l, r) for(int i = (int)(l); i < (int)(r); i++) #define rrange(i, l, r) for(int i = (int)(r)-1; i >= (int)(l); i--) #define rep(i, n) range(i, 0, n) #define rrep(i, n) rrange(i, 0, n) #define len(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sum(a) accumulate(all(a), 0) #define it2idx(a, it) distance(a.begin(), it) #define idx2it(a, idx) next(a.begin(), idx) #define elif else if namespace io { #ifdef LOCAL ofstream dout("./dmp.txt"); #else ofstream dout("/dev/null"); #endif template istream &operator >> (istream &in, pair &a){ in >> a.first >> a.second; return in; } template istream &operator >> (istream &in, vector &a){ for(T &x: a) in >> x; return in; } template ostream &operator << (ostream &out, const pair &a){ out << a.first << " " << a.second; return out; } template ostream &operator << (ostream &out, const vector &a) { rep(i, len(a)) out << a[i] << (i == len(a)-1 ? "" : " "); return out; } template ostream &operator << (ostream &out, const unordered_set &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } template ostream &operator << (ostream &out, const set &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } template ostream &operator << (ostream &out, const multiset &a) { int i = 0; for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; } return out; } inline void print() { cout << "\n"; } template inline void print(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << " "; print(u...); } inline void dmp() { dout << endl; } template inline void dmp(const T &t, const U &...u) { dout << t; if (sizeof...(u)) dout << " "; dmp(u...); } } using namespace io; template inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; } void solve(); constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr int MOD = 1e9+7; //constexpr int MOD = 998244353; int main() { cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15); solve(); return 0; } #pragma endregion // https://ei1333.github.io/library/graph/tree/tree-diameter.hpp #line 2 "graph/tree/tree-diameter.hpp" #line 2 "graph/graph-template.hpp" template struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template struct Graph { vector > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if (weighted) cin >> c; if (directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector > &operator[](const int &k) { return g[k]; } inline const vector > &operator[](const int &k) const { return g[k]; } }; template using Edges = vector >; #line 4 "graph/tree/tree-diameter.hpp" /** * @brief Tree-Diameter(木の直径) * */ template struct TreeDiameter : Graph { public: using Graph::Graph; using Graph::g; vector > path; T build() { to.assign(g.size(), -1); auto p = dfs(0, -1); auto q = dfs(p.second, -1); int now = p.second; while (now != q.second) { for (auto &e : g[now]) { if (to[now] == e.to) { path.emplace_back(e); } } now = to[now]; } return q.first; } explicit TreeDiameter(const Graph &g) : Graph(g) {} private: vector to; pair dfs(int idx, int par) { pair ret(0, idx); for (auto &e : g[idx]) { if (e.to == par) continue; auto cost = dfs(e.to, idx); cost.first += e.cost; if (ret < cost) { ret = cost; to[idx] = e.to; } } return ret; } }; void solve() { int N; cin >> N; TreeDiameter g(N); g.read(N-1, -1, true); cout << g.build() << endl; }