백준 1967 트리의 지름

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

1967번: 트리의 지름

 

1167번 문제와 똑같은 개념

이번엔 입력이 한방향만 주어지므로, 둘다 업데이트시켜줘야됨

##필수개념##

트리의 한 점에서 가장 먼 점은, 항상 지름 중 한 점이다!! https://fuckingcomputer.tistory.com/97 참고

 

##코드##

import sys
from collections import deque
input=sys.stdin.readline

def dfs(start):
    one=1
    long_d=0
    visited=[-1 for _ in range(n+1)]
    que=deque([start])

    visited[start]=0
    while que:
        now=que.popleft()
        for next,weight in tree[now]:
            
            if visited[next]==-1:
                visited[next]=visited[now]+weight
                que.append(next)
                if visited[next]>long_d:
                    long_d=visited[next]
                    one=next
    return one,long_d




    



n=int(input())
tree=[[]for _ in range(n+1)]

#트리 채우기
for _ in range(n-1):
    a,b,c=map(int,input().split())
    tree[a].append((b,c))
    tree[b].append((a,c))

    
one,tresh=dfs(1) #지름중하나, 쓰레기값(거리
print(dfs(one)[1]) #거리만 출력!