34673번 - 한국의 철도

문제

철도를 좋아하는 가희가 사는 한국에는, 1ドル$번 도시부터 $n$번 도시까지 $n$개의 도시가 있으며, $i$번 도시에는 $i$번 역만 있습니다. 열차들은 이 역들에서 운행을 시작하거나 종료할 수 있습니다. 가희는 열차의 운행 방향이 상행과 하행으로 나뉜다는 사실을 알게 되었습니다. 운행을 시작하는 역이 $a$번 도시에 있고, 운행을 종료하는 역이 $b$번 도시에 있다고 할 때, 다음 두 조건 중 하나 이상을 만족하면 상행입니다.

• 1ドル$번 도시에 있는 역부터 $a$번 도시에 있는 역까지의 거리가 1ドル$번 도시에 있는 역부터 $b$번 도시에 있는 역까지의 거리보다 더 멉니다.
• 1ドル$번 도시에 있는 역부터 $a$번 도시에 있는 역까지의 거리와 1ドル$번 도시에 있는 역부터 $b$번 도시에 있는 역까지의 거리가 같습니다. 그리고 $b$번 역이 있는 도시의 인구수보다 $a$번 역이 있는 도시의 인구수가 더 많습니다.

이때, $a$번 도시에 있는 역부터 $b$번 도시에 있는 역까지 거리는 $a$번 도시에 있는 역에서부터 $b$번 도시에 있는 역까지 이동하는 데 이용한 노선 거리의 합의 최소값 입니다. 또한, 상행의 반대 방향은 하행이며 하행의 반대 방향은 상행입니다. 이 방식으로 상행, 하행을 결정할 수 없다면, 상행도 하행도 아닙니다.

운행 정보는 다음과 같이 정의합니다.

• $s$번 역에서 운행을 시작하여, $e$번 역에서 운행을 종료합니다.
• $s ≠ e$

운행을 시작하는 역과 운행을 종료하는 역 중 하나라도 다르다면 다른 운행 정보로 셉니다. 상행으로 운행되는 서로 다른 운행 정보의 개수와, 하행으로 운행되는 서로 다른 운행 정보의 개수를 출력해 주세요.

입력

첫 번째 줄에 도시의 수 $n$이 주어집니다.

두 번째 줄부터 $n-1$개의 줄에 걸쳐 노선 정보 $s,ドル $e,ドル $d$가 공백으로 구분되어 주어집니다. 이는 $s$번 역과 $e$번 역 사이에 거리가 $d$인 양방향으로 연결된 노선이 있음을 의미합니다.

$n+1$번째 줄에 도시의 인구 수 $p_1, p_2, \cdots, p_n$이 공백으로 구분되어 주어집니다.

출력

첫 번째 줄에 상행으로 운행되는 서로 다른 운행 정보의 개수와 하행으로 운행되는 서로 다른 운행 정보의 개수를 공백으로 구분하여 출력해 주세요.

제한

• 2ドル \leq n \leq 4 \times 10^{5}$
• 1ドル \leq s_i, e_i \leq n$
• 1ドル \leq d_i, p_i \leq 10^{9}$
• 입력으로 주어지는 모든 수는 정수입니다.
• 두 역을 연결하는 중복된 노선이 존재하지 않으며, 임의의 서로 다른 두 역은 하나, 혹은 둘 이상의 노선을 이용해서 가는 방법이 존재합니다.
• 모든 노선은 기점과 종점을 제외한 어떠한 역도 경유하지 않습니다.

노트