BOJ : 1967 트리의 지름

문제 : https://www.acmicpc.net/problem/1967

한 노드를 기준으로 가지고 있는 말단 노드를 쫙 땡겼을 때 가장 긴 녀석의 지름을 구하는 문제입니다.

자식 노드가 3개 이상일 수 있다는 것만 조심하시면 DFS로 간단하게 해결 가능합니다.

자식 노드의 가중치의 합을 return 하여 기준 노드에서 가장 긴노드, 두 번째 노드를 구해서 더한 값이 지름이 됩니다.

#include <cstdio>
#include <vector>
using namespace std;

int N, ans=0;
vector<pair<int, int>> v[10001];

int dfs(int start){
    int fst=0, snd=0, sum;
    for (auto n : v[start]){
        //printf("%d %d\n",start,n.second+len);
        sum = dfs(n.first) + n.second;
        if(sum > fst) {
            snd = fst;
            fst = sum;
        }
        else if (sum > snd) snd = sum;
    }
    if(ans < (fst + snd)) ans = fst+snd;
    return fst;
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        v[a].push_back(make_pair(b, w));
    }
    
    dfs(1);
    
    printf("%d\n",ans);
}