DFS

루트가 있는 트리가 정점 $n$개로 주어지며, $r$은 트리의 루트이다. 각 정점 $x$의 값은 $a_x$이다.

정점 $x$에서 시작해 $y$를 찾는 DFS 과정을 다음과 같이 정의한다.

1. $x$를 스택에 넣는다.
2. 스택의 맨 위 원소 $w$를 확인한다. $w = y$이면 과정이 끝난다. 그렇지 않고 $w$의 방문하지 않은 자식이 하나 이상 있으면, 그중 하나를 같은 확률로 골라 스택에 넣는다.
3. 방문하지 않은 자식이 없을 때까지 2단계를 반복한다.
4. 스택의 맨 위 원소를 꺼낸다.
5. 스택이 빌 때까지 2단계를 반복한다.

이 과정은 $y$가 $x$의 서브트리에 속할 때에만 합법이다.

$f(x,y)$는 $x$에서 시작해 $y$를 찾는 DFS 과정 동안 스택에 한 번이라도 들어간 모든 정점 값의 최솟값의 기댓값이다.

이제 모든 합법적인 쌍 $(x,y)$에 대해 $\sum f(x,y)$를 구한다. 답은 기약분수 $\frac{x}{y}$로 나타낼 수 있으며, $x$와 $y$는 정수이고 $y\not\equiv 0\pmod{998\,244\,353}$이다. $x\cdot y^{-1}\pmod{998\,244\,353}$의 값을 출력한다. 즉, $0\leq a<998\,244\,353$이고 $a\cdot y\equiv x\pmod{998\,244\,353}$을 만족하는 정수 $a$를 출력한다.

첫 줄에 테스트 케이스 수 $T$ ($1 \leq T \leq 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정점 수 $n$과 루트 $r$ ($1 \leq n \leq 4 \cdot 10^5$, $1 \leq r \leq n$)이 주어진다.

다음 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 정점 $i$의 값 $a_i$ ($1\leq a_i\leq 10^9$)이다.

이어서 $n-1$개의 줄에 간선을 나타내는 정수 $u$, $v$ ($1 \leq u,v \leq n$)가 주어진다.

$\sum n \leq 8 \cdot 10^5$이며, 주어진 그래프는 트리이다.

각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.