https://www.acmicpc.net/problem/1967
1967번: 트리의 지름파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연www.acmicpc.net
1167번 문제와 똑같은 개념
이번엔 입력이 한방향만 주어지므로, 둘다 업데이트시켜줘야됨
##필수개념##
트리의 한 점에서 가장 먼 점은, 항상 지름 중 한 점이다!! https://fuckingcomputer.tistory.com/97 참고
##코드##
import sysfrom collections import dequeinput=sys.stdin.readlinedef 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]) #거리만 출력!