[백준] 1967번 트리의 지름 (gold 4

import java.io.*;
import java.util.*;

class Point{
    int node;
    int v;
    public Point(int node, int v){
        this.node=node;
        this.v=v;
    }
}
public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.valueOf(br.readLine());
        StringTokenizer st;

        ArrayList<Point>[] arr=new ArrayList[n+1];
        ArrayList<Integer>[] length=new ArrayList[n+1];
        for(int i=1; i<=n; i++){
            arr[i]=new ArrayList<>();
            length[i]=new ArrayList<>();
        }

        int[] visit=new int[n+1];
        //child에 parent넣고, 밑에서부터 올라오면서 찾기.
        for(int i=1; i<n; i++){
            st=new StringTokenizer(br.readLine());
            int parent=Integer.valueOf(st.nextToken());
            int child=Integer.valueOf(st.nextToken());
            int v=Integer.valueOf(st.nextToken());
            //자식 노드의 갯수 구하기.
            //bfs에서 자식을 다 방문하고 부모를 방문해야한다.
            //만약 자식 하나 방문하고, 부모 방문하고 다시 해당 노드의 자식을 방문하면
            //그 노드를 재방문하게 됨.
            visit[parent]++;
            arr[child].add(new Point(parent,v));
        }

        //젤 밑단 노드들 먼저 que에 넣기
        Queue<Integer> que=new LinkedList<>();
        for(int i=2; i<=n; i++){
            if(visit[i]==0){
                que.offer(i);
            }
        }

        //노드 거꾸로. 마지막에서 부터 위로 올라가는 양상으로 길이들 구하는 것이므로.
        while(!que.isEmpty()){
            int temp=que.poll();
            if(temp==1){
                continue;
            }
            Point p=arr[temp].get(0);
            //자식 노드한개 제거 0되면 que에넣기
            visit[p.node]--;
            //자식이 없는 경우. 이땐 다음노드에 이동거리만큼만 추가.
            if(length[temp].size()==0) {
                length[p.node].add(p.v);
            }
            //자식 노드들의 길이가 있는 경우.
            //큰 값을 더 위의 부모노드로 올리면되므로, 정렬하여 큰 값에 이동거리를 더하여 올린다.
            else{
                Collections.sort(length[temp]);
                length[p.node].add(length[temp].get(length[temp].size()-1)+p.v);
            }
            if(visit[p.node]==0) {
                que.offer(p.node);
            }
        }

        int max=0;
        for(int i=1; i<=n; i++){
            int temp=0;
            Collections.sort(length[i]);
            //길이가 2개이상이면 큰 값 두개를 더하면됨. 자식이 2개 있는 경우
            if(length[i].size()>=2) {
                temp = length[i].get(length[i].size() - 1) + length[i].get(length[i].size() - 2);
            }
            //자식이 한개만 있는 경우도 있을 수 있다.
            else if(length[i].size()==1){
                temp=length[i].get(0);
            }
            max = max < temp ? temp : max;
        }

        bw.write(max+"");
        bw.flush();

    }
}

//문제를 완전히 잘못 이해했다. 노드의 번호가 위에서 아래로 작아지는, 깔끔하게 순서대로 떨어지는줄 알았는데,
//그런 상황이 아니라, 번호가 부모, 자식간에 무작위로 나올 수 있었다.. 1번만 루트노드 확정..