33947번 - 특별한 정점

문제

1ドル$부터 $N$까지 $N$개의 정점으로 이루어진 무방향 트리가 있다.

트리에는 특별한 정점이 있다. 트리에 간선을 추가해서 모든 특별한 정점을 한 번씩 방문하는 경로를 만들려고 한다. 이때 같은 정점을 두 번 방문해서는 안된다. 특별한 정점이 아닌 일반 정점은 경로상에 포함될 수 있지만, 모든 일반 정점을 방문할 필요는 없다.

모든 특별한 정점을 한 번씩 방문하는 경로를 만들기 위해 필요한 간선의 최소 개수를 구해보자.

입력

첫째 줄에 정점의 개수 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

둘째 줄부터 $N-1$개의 줄에 걸쳐 간선이 연결하는 두 정점의 번호 $u,v$가 주어진다. $(1 \leq u,v \leq N)$

$N+1$번째 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 정수가 0ドル$이면 $i$번 정점은 일반 정점이며, 1ドル$이면 $i$번 정점은 특별한 정점이다.

입력으로 주어지는 그래프는 트리이다.

출력

경로를 만들기 위해 추가해야 할 간선의 최소 개수를 출력한다.

제한

힌트