http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1317 The longest path on tree

gistfile1.cpp

#include <cassert>
#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <functional>
#include <algorithm>

const int N = 50000;

int edgeCount, firstEdge[N], to[N << 1], nextEdge[N << 1], length[N << 1];

void addEdge(int u, int v, int w) {
    to[edgeCount] = v;
    length[edgeCount] = w;
    nextEdge[edgeCount] = firstEdge[u];
    firstEdge[u] = edgeCount ++;
}

int answer;

int search(int p, int u) {
    std::vector <int> paths(1, 0);
    for (int iter = firstEdge[u]; iter != -1; iter = nextEdge[iter]) {
        int v = to[iter];
        if (v != p) {
            paths.push_back(search(u, v) + length[iter]);
        }
    }
    std::sort(paths.begin(), paths.end(), std::greater <int>());
    if ((int)paths.size() >= 2) {
        answer = std::max(answer, paths[0] + paths[1]);
    }
    return paths[0];
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        assert(n - 1 == m);
        edgeCount = 0;
        memset(firstEdge, -1, sizeof(firstEdge));
        for (int i = 0; i < n - 1; ++ i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            a --, b --;
            addEdge(a, b, c);
            addEdge(b, a, c);
        }
        answer = INT_MIN;
        search(-1, 0);
        printf("%d\n", answer);
    }
    return 0;
}