TIOJ 1213 5樹論 之 最遠距點對

找樹的直徑

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<utility>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
typedef pair<int,int> pii;
vector<pii> link[N];
int H[N];
int n;
int dfs(int fat, int prc){
    vector<int> hv;
    int get_r = 0;
    for(int lx = 0;lx < link[prc].size();lx++){
        int ind = link[prc][lx].first;
        if(fat == ind) continue;
        get_r = max(get_r, dfs(prc, ind));
        hv.push_back(H[ind] + link[prc][lx].second);
    }
    sort(hv.begin(), hv.end());
    int hvc = hv.size();
    if(hvc == 0)
        H[prc] = 0;
    else
        H[prc] = hv[hvc-1];
    if(hvc == 1)
        get_r = max(get_r, hv[hvc-1]);
    else if(hvc >= 2)
        get_r = max(get_r, hv[hvc-1] + hv[hvc-2]);
    return get_r;
}
int main(){
    for(;;){
        scanf("%d", &n);
        if(n == 0)break;
        memset(H, 0, sizeof(H));
        for(int lx=  0;lx < n;lx++)
            link[lx].clear();
        for(int lx = 0;lx < n-1;lx++){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c); a--, b--;
            link[a].push_back(pii(b, c));
            link[b].push_back(pii(a, c));
        }

        printf("%d\n", dfs(-1, 0));
    }
    return 0;
}