25760번 - 귀경길 교통상황을 알려드립니다

문제

정현이가 살고 있는 나라에는 각 지역을 연결하는 도로망이 있다. 도로망은 총 $N$개의 지점과 두 지점을 연결하는 $N-1$개의 양방향 도로로 구성되어 있으며, 모든 두 지점 사이를 도로망으로 이동할 수 있다. 그리고 한 지점에는 도로망을 이용하고 있는 차량이 최대 1ドル$대 존재할 수 있다.

추석 연휴가 끝나고 수많은 차량들이 도로망을 통해 집으로 돌아가고 있다. 1ドル$번 지점에는 도로망을 빠져나가 집으로 갈 수 있는 톨게이트가 존재하고, 모든 차량들은 도로망을 빠져나가기 위해 1ドル$번 지점으로 향하고 있다.

1ドル$분이 지날 때마다 각 차량은 아래 세 가지 행동 중 하나를 한다.

1. 이동하지 않고 대기한다.
2. 자신이 1ドル$번 지점에 있다면 톨게이트를 통해 도로망을 빠져나간다.
3. 자신이 있는 지점과 인접한 다른 지점으로 이동한다. 단, 각 지점에는 차량이 최대 1ドル$대 존재할 수 있으므로, 그 지점에 이동하지 않고 대기하는 차량이 존재하거나 다른 지점에서 그 지점으로 이동하는 다른 차량이 존재한다면 해당 지점으로 이동할 수 없다.

도로망에 차량이 많아지면서 교통체증이 극심해지고 있다. 귀경길 도로 위에서 몇시간째 갇혀있는 정현이는 차량들이 최적으로 움직일 때, 모든 차량이 도로망을 빠져나가는데 몇 분이 소요될지 궁금해졌다.

도로망의 구성과 0ドル$분에 존재하는 차량들의 위치가 주어졌을 때, 정현이의 의문을 해결해주는 프로그램을 작성해보자.

입력

첫째 줄에 도로망에 존재하는 지점의 수 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

둘째 줄부터 $N-1$줄에 걸쳐, 도로망의 두 지점을 연결하는 도로 정보 $(u_i, v_i)$가 한 줄씩 주어진다. 이는 $u_i$번 지점과 $v_i$번 지점을 연결하는 도로가 존재한다는 것이다. $(1 \leq u_i \leq N, 1 \leq v_i \leq N, u_i \not = v_i)$

$N+1$번째 줄에 1ドル$번 지점부터 $N$번 지점까지 그 지점에 차량이 존재하는지 여부를 나타내는 정수 $C_i$가 공백으로 나뉘어 주어진다. $i$번 지점에 차량이 존재한다면 $C_i$는 1ドル$이고, 그렇지 않다면 0ドル$이다.

도로망에는 차량이 적어도 한 대 이상 존재함이 보장된다.

출력

첫째 줄에 차량들이 최적으로 행동할 때 모든 차량이 도로망을 빠져나가는데 걸리는 시간을 출력한다.

제한

힌트