31032번 - 트리의 개수

경기과학고등학교는 연말을 맞아 대학습실에 설치되어 있던 나무를 부활시켜 크리스마스 트리를 설치했다! 이번에 설치한 트리 $T$는 정점이 $N$개이고, $i$번 정점의 내구성이 $A_i$이다. 정점이 $N$개인 트리는 간선이 $N-1$개인 연결 그래프이다. 각 정점의 내구성은 $1$ 이상 $K$ 이하이다. $T$의 부분 트리는 $T$의 하나 이상의 정점과 0개 이상의 간선을 골라 만든 트리를 의미한다. 정점이 하나인 그래프도 트리이다.

• 정후: 동현아, 크리스마스 트리야!
• 동현: 그렇네! 이 트리 $T$의 부분 트리 $T'$가 썩어서 내구성 $A_i \leq j$인 모든 정점 $i$와 그 정점에 연결된 간선이 없어지게 되면, $T'$는 $f_j(T')$ 개(단, 모두 없어진다면 $f_j(T')=0$)로 분할되겠지?
• 정후: 그렇구나! 그렇다면 $T$의 모든 부분 트리 $T'$에 대해 $f_j(T')$의 합을 $g_j(T)$라고 할 때, $\sum_{j=1}^K g_j(T)$의 값을 $998\,244\,353$으로 나눈 나머지는 얼마일까?
• 동현: 아! 그건 $O(N^2)$ 미만에 해결할 수 있을 것 같아!

어떻게 해결한다는 걸까? 여러분이 한번 풀어 보자.

첫 번째 줄에 $N$과 $K$가 주어진다. 두 번째 줄에 $A_1, A_2, \cdots, A_N$이 주어진다. 세 번째 줄부터 $N+1$번째 줄까지 트리의 간선이 연결하는 두 정점의 번호 $u, v$가 주어진다. 모든 정점에서 다른 모든 정점으로 간선을 통해 이동할 수 있다.

$\sum_{j=1}^K g_j(T)$를 $998\,244\,353$으로 나눈 나머지를 출력한다.

• $1\leq N\leq 3\times 10^5$
• $1\leq K\leq 10^9$
• $1\leq A_i\leq K$
• $1\leq u, v\leq N$, $u\neq v$
• 주어지는 모든 수는 정수이다.