树的最长路径，即求一颗树的直径问题，dfs和bfs都可一解决，但一直觉得dfs的比较绕，不好理解。

于是写了bfs的方法，其中0节点当作哨兵，每次从队列中取出0节点的时候，就知道一轮bfs结束，可以把深度加一。

bfs的思路很简单：

1.随便找一个节点，以该节点为起点进行一次bfs，得出的最后一个顶点，一定是直径的一端。

2.再以这个直径的一端为起点进行一次bfs，得出的直径的另一端，然后这两个端点之间即为直径（最长路径）。

刚开始老是WA，后来发现是因为忘记把顶点标记清零了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 vector
           
             tree[100010];10 bool used[100010];11 int N;12 int ans;13 14 int bfs(int num)15 {16 ans = 0;17 memset(used, 0, sizeof(used));18 int point;19 queue
            
              q; 20 q.push(num);21 q.push(0);22 while (!q.empty()) {23 int p = q.front();24 q.pop();25 26 if (p == 0 && !q.empty()) {27 ans++;28 q.push(0); 29 continue;30 }31 else if (p==0) {32 break;33 }34 35 for (size_t i = 0; i < tree[p].size(); ++i) {36 if (!used[tree[p][i]]) {37 q.push(tree[p][i]);38 used[tree[p][i]] = true;39 }40 }41 42 point = p;43 }44 45 return point;46 }47 48 int main()49 {50 int u,v;51 scanf("%d", &N);52 for (int i = 1; i < N; ++i) {53 scanf("%d%d", &u, &v);54 tree[u].push_back(v);55 tree[v].push_back(u);56 }57 bfs(bfs(1));58 printf("%d\n", ans);59 return 0;60 }