시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB137675773.077%

문제

$N$개의 정점으로 이루어진 트리가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있다. 정점에는 색깔이 있는데 모든 정점은 빨간색 혹은 파란색이다. 이때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

  • u : 임의의 빨간색 정점과 파란색 정점을 연결하는 단순 경로 중에서 $u$번 정점을 경유하는 경로의 개수를 출력한다. 경로에는 방향성이 없으며, 어떤 경로가 $u$번 정점을 경유한다는 것은 경로가 시작이나 끝이 아닌 중간에 $u$번 정점을 지난다는 것이다.

입력

첫째 줄에 트리의 크기 $N(1\le N \le 100\ 000)$이 주어진다.

두 번째 줄에 정수 $a_1, a_2, …, a_N$이 주어진다. $a_i(0 \le a_i \le 1)$는 $i$번째 정점의 색깔이며, $1$은 빨간색을, $0$은 파란색을 의미한다.

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

$N + 2$번째 줄에 쿼리의 개수 $Q(1\le Q \le N)$가 주어진다.

$N + 3$번째 줄부터 $Q$개의 줄에 쿼리가 주어진다.

쿼리는 하나의 정수 $u(1 \le u \le N)$로 이루어져 있다.

출력

쿼리의 수행 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
1 1 1 0 0
1 3
3 2
3 4
3 5
3
2
3
4

예제 출력 1

0
4
0

예제 입력 2

7
1 0 1 1 1 0 0
1 2
1 3
2 4
2 5
3 6
3 7
3
1
2
3

예제 출력 2

5
4
6

출처

University > 충남대학교 > 2022 충남대학교 SW-IT Contest - Division 1 K번