POJ 2631 Roads in the North （树的直径）

题意：

给定一棵树， 求树的直径。

分析：

两种方法：

1.两次bfs， 第一次求出最远的点， 第二次求该点的最远距离就是直径。

2.同hdu2196的第一次dfs， 求出每个节点到子树的最长距离和次长距离， 然后某个点的最长+次长就是直径。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const int maxn = 12000 + 7;
const int inf = 1e9 + 7;
int Max[maxn];// 最大距离
int sMax[maxn];// 次大距离
struct Edge {
    int v, d;
};
vector<Edge> G[maxn];
int N = 1;
void init() {
    for(int i = 0; i < maxn; i ++) {
        G[i].clear();
    }
}
void dfs1(int u, int pre) {//更新u本身
    Max[u] = sMax[u] = 0;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v, d = G[u][i].d;
        if(v == pre)
            continue; //不经过父亲， 只搜索子树
        dfs1(v, u); //一直搜到叶子再回溯， 因为是根据孩子的Max更新自己的Max
        if(sMax[u] < Max[v] + d) { //如果u的次长距离 < 到v的距离  + v的最大距离
            //更新距离
            sMax[u] = Max[v] + d;
            if(sMax[u] > Max[u]) { //如果次长距离大于最长距离， 交换二者位置
                swap(sMax[u], Max[u]);
            }
        }
    }
}

int u, v, d;
int main() {
    while(cin >> u >> v >> d) {
        N++;
        G[u].push_back((Edge) {v,d});
        G[v].push_back((Edge) {u,d});
    }
    dfs1(1, -1);

    int ans = -inf;
    for(int i = 1; i <= N; i++) {
        ans = max(ans, Max[i] + sMax[i]);
    }
    cout << ans << "
";
    return 0;
}