You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.
Input
The first line of the input file contains one integer N — number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree — Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).
Output
Print the length of the longest path on one line.
Sample Input
3 1 2 2 3
Sample Output
2
解题思路
用vector储存树，然后由无向树的性质可从任意一个点进行一次DFS，在DFS的过程中记录从该节点出发的路径的最长值并返回，由于当前点不是最长路径的出发结点，可能是最长路径中的某一点。于是在对每一个点进行DFS时记录子路径的最长值和次长值并与当前最长路径比较，即可得出结果。
AC代码：
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) const int MAXN = 10005; int n,x,y,ans=0; vector<int> v[MAXN]; bool vis[MAXN]; int dfs(int x,int y) { int len=v[x].size(),ans1=0,ans2=0; for(int i=0;i<len;i++) { if(v[x][i]==y) continue; int t=dfs(v[x][i],x); if(t>ans1) ans2=ans1,ans1=t; else if(t>ans2) ans2=t; } if(ans1+ans2 > ans) ans=ans1+ans2; return ans1+1; } int main() { SIS; cin >> n; for(int i=1;i<n;i++) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } dfs(1,0); cout << ans << endl; return 0; }