25638번 - 트리와 경로 개수 쿼리

$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)$로 이루어져 있다.

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