B4016 树的直径 - 洛谷

题目描述

给定一棵 n 个结点的树，树没有边权。请求出树的直径是多少，即树上最长的不重复经过一个点的路径长度是多少。

输入格式

第一行输入一个正整数 n，表示结点个数。
第二行开始，往下一共 n - 1 行，每一行两个正整数 (u, v)，表示一条边。

输出格式

输出一行，表示树的直径是多少。

输入输出样例

输入 #1	输出 #1
5 1 2 2 4 4 5 2 3	3

说明/提示

数据保证，1≤n≤1e5

代码：

#include<bits/stdc++.h>
using namespace std;
int n, start, step; 
vector<int> G[100000];  void dfs(int cur, int fa, int cnt) {if (cnt > step) {start = cur;step = cnt;}for (auto to : G[cur]) {  if (to == fa) continue;dfs(to, cur, cnt + 1);}
}int main() {cin >> n;for (int i = 1; i < n; i++) { int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u); }dfs(1, -1, 0);step = 0; dfs(start, -1, 0);cout << step << endl;return 0;
}