30998번 - 최고의 크리스마스트리

문제

현아는 크리스마스트리를 준비하고 있다. 현아는 자신이 준비한 트리가 세상에서 가장 예뻤으면 좋겠다.

현아가 가진 트리 $T$는 $n$개의 정점과 $n-1$개의 간선으로 구성되어 있고 루트 $r$을 가진다. 또한 현아는 각 정점을 꾸밀 장식 $n$개를 갖고 있다. 모든 장식은 저마다 고유한 예쁨의 값을 가져서, 첫 번째로 예쁜 장식, 두 번째로 예쁜 장식, $\cdots,ドル $n$번째로 예쁜 장식이 존재한다. 어떤 두 장식도 예쁨의 값이 같지 않다. 트리의 각 정점에 달린 장식이 다음 조건을 만족시킬 때, $T$는 예쁘다고 한다.

• $r$을 기준으로 형성되는 모든 부모-자식 쌍에 대하여, 자식 정점에 달린 장식이 부모 정점에 달린 장식보다 예쁨의 값이 크다.

이때 두 정점 $u,ドル $v$에 대하여 $u$가 $v$의 부모라는 것은 두 정점이 인접하고, 루트 $r$에 대하여 $r$과 $u$ 사이의 거리가 $r$과 $v$ 사이의 거리보다 작다는 것이다. 트리에서 두 정점 $u,ドル $v$ 사이의 거리는 $u$에서 $v$까지 간선을 따라 이동할 때 사용한 간선의 최소 개수로 정의한다.

$T$가 예쁘도록 각 정점에 장식을 다는 경우의 수를 998ドル,244円,353円$으로 나눈 나머지를 구하라. 998ドル,244円,353円$은 소수이다. 장식이 달리지 않은 정점은 없어야 한다. 한 번만 구하면 재미없으니, 트리의 루트를 바꾸어 가며 $Q$번 구하라.

입력

첫 번째 줄에 트리 정점의 수 $n$이 주어진다.

그다음 줄부터 $n-1$개의 줄에 걸쳐 정수 $u, v$가 공백으로 구분되어 주어진다. 이는 두 정점 $u$와 $v$를 잇는 간선이 존재한다는 뜻이다.

그다음 줄에 쿼리의 수 $Q$가 주어진다.

그다음 줄부터 한 줄에 하나씩 정수 $r$이 주어진다. 이는 트리의 루트가 $r$일 때 문제의 답을 요청하는 쿼리를 의미한다.

출력

쿼리가 들어올 때마다 답을 출력한다. 답과 답 사이에는 하나의 개행 문자가 존재해야 한다.

제한

• 2ドル \leq n \leq 200,000円$
• 1ドル \leq u, v \leq n, u \neq v$
• 1ドル \leq Q \leq 200,000円$
• 1ドル \leq r \leq n$
• 주어지는 그래프는 반드시 트리이다.

힌트