7303 : 트리 직경
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치가 있는 트리에서 임의의 두 노드 사이의 거리 중 가장 긴 거리(트리의 지름)를 구하십시오.
트리의 지름은 BFS 또는 DFS를 두 번 수행하여 구할 수 있습니다.
알고리즘: 임의의 노드에서 가장 먼 노드 $u$를 찾고, $u$에서 가장 먼 노드까지의 거리가 트리의 지름입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
트리의 지름은 BFS 또는 DFS를 두 번 수행하여 구할 수 있습니다.
알고리즘: 임의의 노드에서 가장 먼 노드 $u$를 찾고, $u$에서 가장 먼 노드까지의 거리가 트리의 지름입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정점의 개수 $V$가 주어집니다. ($2 \le V \le 100{,}000$)
둘째 줄부터 간선 정보
둘째 줄부터 간선 정보
u v w가 주어집니다. ($u$와 $v$ 사이 간선의 가중치 $w$)출력 설명
트리에서 임의의 두 노드 사이의 거리 중 가장 긴 거리(트리의 지름)를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2 3
2 3 2
2 4 1
4 5 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
10도움
BFS/DFS를 두 번 수행합니다. 1번에서 BFS → 가장 먼 노드 $u$ 발견 → $u$에서 BFS → 가장 먼 거리가 트리의 지름입니다.