Opening Time

시간 제한2초메모리 제한1024 MB

요약
가중치 트리에서 각 정점 x마다, 모든 정점 i에 대해 i에서 x와 선택한 정점 y 중 가까운 쪽까지의 거리의 최댓값을 최소로 만드는 값을 구한다.
난이도

어려움10점 중 9점

유형
트리, 분할 정복, 그리디, 이분 탐색
정답자
아직 제출이 없습니다

문제

키보토스의 블랙마켓은 NN개의 구역과, 구역 사이를 잇는 N−1N-1개의 도로로 이루어져 있다. ii번 도로는 구역 A_iA\_i와 B_iB\_i를 W_iW\_i의 길이로 잇는 도로이다. 또한, 임의의 두 구역 사이에는 항상 유일한 경로가 존재한다. 즉, 블랙마켓은 트리 구조를 이룬다.

xx번 구역에는 상점 xx가 위치해 있다. 내일, 상점은 처음으로 개점을 할 것이다. 첫 개점이기 때문에, 모든 NN개의 구역으로부터 이 상점을 방문하기 위해 이동할 것이다. 하지만 사람이 한 곳에 너무 많이 몰리면 불만이 생길 수 있으므로, 한 구역에 가맹점을 하나 설치해, 각 구역에서는 본점과 가맹점 중 더 가까운 곳을 방문하게 하려고 한다. 모든 구역의 접근성을 고려하여, 다음 값을 최소화하려고 한다. 이 때, yy는 가맹점의 위치이다.

max⁡_1≤i≤N(min⁡(distance(x, i), distance(y, i)))\displaystyle \max\limits\_{1 \le i \le N}(\min(\textrm{distance}(x,\ i),\ \textrm{distance}(y,\ i))) (단, distance(a, b)\textrm{distance}(a,\ b)는 구역 aa와 구역 bb 사이의 거리)

x=1,2,⋯ ,Nx = 1, 2,\cdots, N 에 대해, 적절히 가맹점을 잡았을 때 위 식의 최솟값을 구해주자.

입력

첫 번째 줄에 양의 정수 NN이 주어진다. (2≤N≤105)(2\le N\le 10^5)

두 번째 줄부터 N−1N-1개의 줄에 걸쳐 세 양의 정수 A_i,B_i,W_iA\_i, B\_i, W\_i가 공백을 사이에 두고 주어진다. (1≤A_i,B_i≤N; A_i≠B_i; 1≤W_i≤109)(1\le A\_i, B\_i\le N;\ A\_i\neq B\_i;\ 1\le W\_i\le 10^9)

출력

NN개의 정수를 공백을 사이에 두고 출력한다. ii번째 정수는 x=ix=i일 때의 위 식의 최솟값을 뜻한다.

예제1

  1. 예제 1

    입력
    5
1 2 7
2 3 5
1 4 3
4 5 3
    예상 출력
    6 5 5 5 6