정점들의 집합 \(V\,(\neq \varnothing)\)와 간선들의 집합 \(E\)를 가진 그래프 \(T=(V,E)\)가 트리라 함은 \(T\)의 임의의 두 정점 \(u\)와 \(v\) 사이에 항상 경로가 존재하고 그 경로는 하나뿐인 경우이다.

트리 \(T=(V,E)\) 안의 서브트리 \(S=(\overline{V},\overline{E})\)란, \(\overline{V}\subseteq V\), \(\overline{E}\subseteq E\) 이면서 위의 트리의 성질을 만족하는 그 자체로 트리인 그래프이다.

그런데 트리 \(T\)의 어떤 정점들에는 검은 돌이 놓여있다. 검은 돌은 한 정점에 많아야 하나씩만 놓일 수 있다.

우리는 다음과 같은 질의 \(q=(i,j)\)를 던질 것이고 여러분들은 이 질의에 답해야 한다.

• 트리 \(T\) 안에 정확히 \(i\)개의 정점을 가지고 이중에 \(j\)개의 정점에 검은 돌이 놓여 있는 서브트리 \(S\)가 존재하는가?

예를 들어서, 아래 〈그림 1〉에서 9개 정점을 가진 트리가 주어졌다. 여기서 질의 \(q=(5,3)\)에 대해서 위의 조건을 만족하는 정점 \(1,2,3,4,6\)으로 이루어진 서브트리가 존재한다. 하지만 질의 \(q=(4,3)\)에 대해서는 조건을 만족하는 서브트리가 존재하지 않는다.

\(N\)개의 정점을 가진 트리와 \(Q\)개의 질의 \(q\)가 주어질 때, 각각의 질의에 대한 답 중에서 '존재한다'는 답의 총 개수를 출력하시오.

표준 입력으로 다음 정보가 주어진다. 입력의 첫 줄에는 트리 \(T\)의 정점의 개수를 나타내는 정수 \(N\,(1 \le N \le 5{,}000)\)과 정점들에 놓여있는 검은 돌의 개수 \(B\,(0 \le B \le N)\)가 주어진다. 여기서, 트리 \(T\)의 정점은 \(1\)부터 \(N\)까지 정수로 나타낸다. 두 번째 줄에는 검은 돌이 놓여 있는 정점을 나타내는 \(B\)개의 정수 \(x\,(1 \le x \le N)\)가 주어진다. 이어지는 \(N-1\)개 줄 각각에 \(T\)에서 간선이 존재하는 두 정점을 나타내는 정수 \(u,\,v\,(1 \le u,v \le N)\)가 주어진다. 다음 줄에는 질의의 개수 \(Q\,(1 \le Q \le 1{,}000{,}000)\)가 주어지고, 이어지는 \(Q\)개의 줄 각각에 하나의 질의 \(q=(i,j)\)를 나타내는 두 정수 \(i,\,j\,(1 \le i \le N,\ 0 \le j \le \min(i,B))\)가 주어진다.

표준 출력으로 각각의 질의에 대한 답 중에서 '존재한다'는 답의 총 개수를 출력한다.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 고등부 3번