31447번 - 눈덩이 굴리기

문제

눈덩이 굴리기

$N$개의 지점이 $N-1$개의 길로 연결되어 있는 트리 형태의 코스가 있다. 지점들은 1ドル$부터 $N$까지 각각 하나씩 번호가 붙어있다. $N$명의 선수들은 각 지점에 한 명씩 배치되고, $i$번 지점에 있는 선수는 무게가 $W_i$인 눈덩이를 굴리며 모두 같은 도착 지점을 향해 최단 경로로 나아간다. 어떤 선수가 무게 $w$의 눈덩이를 굴리며 길 하나를 지나려면 $w$만큼의 노력이 필요하다.

여러분은 다음과 같은 방법으로 대회를 개최하려 한다.

• 각 지점의 눈덩이 무게 $W_i$를 $L_i$ 이상 $R_i$ 이하의 원하는 정수로 정한다.
• $W_i$를 모두 정한 뒤, 도착 지점을 다음과 같이 정한다. 모든 선수가 도착 지점에 도달하기까지 들인 노력의 합이 가장 작아지도록 하는 지점 $C$를 도착 지점으로 택한다. 이러한 조건을 만족하는 도착 지점은 여러 개 있을 수 있다.

각 지점의 눈덩이 무게를 적절히 정할 때, 도착 지점이 될 수 있는 정점들을 모두 찾아보자.

입력

첫째 줄에 지점의 개수 $N$이 주어진다. $(2 \le N \le 300,000円)$

둘째 줄부터 $N-1$개의 줄에 길로 연결된 두 지점의 번호 $u,ドル $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N)$

다음 $N$개의 줄에 각 지점의 눈덩이 무게의 범위를 나타내는 두 정수 $L_i,ドル $R_i$가 공백으로 구분되어 주어진다. $(1 \le L_i \le R_i \le 10^8)$

출력

각 지점의 눈덩이 무게를 적절히 정할 때, $C$가 될 수 있는 모든 지점의 번호를 공백으로 구분하여 오름차순으로 출력한다. 주어진 제약 조건에서 답은 항상 하나 이상이다.

제한

힌트