특별한 정점

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

요약
일부 정점이 특별한 정점으로 표시된 트리에서, 모든 특별한 정점을 한 번씩 지나는 단순 경로를 만들기 위해 추가해야 하는 간선의 최소 개수를 구한다.
난이도

보통10점 중 7점

유형
트리, DFS, 그리디, 동적 계획법
정답자
아직 제출이 없습니다

문제

11부터 NN까지 NN개의 정점으로 이루어진 무방향 트리가 있다.

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

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

입력

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

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

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

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

출력

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

예제3

  1. 예제 1

    입력
    21
1 2
1 3
2 4
2 5
3 6
3 7
3 8
3 9
4 10
5 11
5 12
6 13
6 14
10 15
10 16
13 17
16 18
16 19
17 20
17 21
0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0
    예상 출력
    4

  2. 예제 2

    입력
    4
1 2
2 3
3 4
0 0 0 0
    예상 출력
    0

  3. 예제 3

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