#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 500000; struct Edge { int to; ll cost; Edge(int to = -1, ll cost = -1) { this->to = to; this->cost = cost; } }; vector E[MAX_V]; struct Node { int v; ll cost; Node(int v = -1, ll cost = -1) { this->v = v; this->cost = cost; } }; class Tree { public: int nodeCnt; Tree(int nodeCnt = MAX_V) { this->nodeCnt = nodeCnt; } void addEdge(int from, int to, ll cost = 1) { E[from].push_back(Edge(to, cost)); } vector diameter(int from = 0) { int u = findFarthestVertex(from); int v = findFarthestVertex(u); return findPath(u, v); } ll calcPathCost(vector &path) { ll totalCost = 0; for (int i = 0; i < path.size() - 1; ++i) { int u = path[i]; int v = path[i + 1]; for (int j = 0; j < E[u].size(); ++j) { if (E[u][j].to == v) { totalCost += E[u][j].cost; } } } return totalCost; } vector findPath(int from, int to) { queue que; que.push(Node(from, 0)); int parent[nodeCnt]; bool visited[nodeCnt]; memset(visited, false, sizeof(visited)); while (!que.empty()) { Node node = que.front(); que.pop(); visited[node.v] = true; if (node.v == to) { vector path; int cur = node.v; while (cur != from) { path.push_back(cur); cur = parent[cur]; } path.push_back(from); reverse(path.begin(), path.end()); return path; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; if (visited[edge.to]) continue; parent[edge.to] = node.v; que.push(Node(edge.to, node.cost + edge.cost)); } } return vector(); } private: int findFarthestVertex(int from) { queue que; que.push(Node(from, 0)); bool visited[MAX_V]; memset(visited, false, sizeof(visited)); ll maxCost = INT_MIN; int farthestV = -1; while (!que.empty()) { Node node = que.front(); que.pop(); if (visited[node.v]) continue; visited[node.v] = true; if (maxCost < node.cost) { maxCost = node.cost; farthestV = node.v; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; Node next(edge.to, node.cost + edge.cost); que.push(next); } } return farthestV; } }; int main() { int N; cin >> N; Tree tree; int a, b; for (int i = 0; i < N - 1; ++i) { cin >> a >> b; --a; --b; tree.addEdge(a, b); tree.addEdge(b, a); } vector path = tree.diameter(); int ans = 2 * (N - 1) - path.size() + 1; cout << ans << endl; return 0; }