트리의 개수

시간 제한2초메모리 제한1024 MB

요약

정점마다 내구도가 주어진 트리에서, 모든 부분트리에 대해 내구도가 j 이하인 정점을 지운 뒤 남는 조각 수를 j=1부터 K까지 더한 값을 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

정후: 동현아, 크리스마스 트리야!

동현: 그렇네! 이 트리 $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$
주어지는 모든 수는 정수이다.

예제2

예제 1
입력
```
4 3
1 2 1 3
1 2
2 3
2 4
```
예상 출력
```
14
```
예제 2
입력
```
5 6
5 3 5 1 2
1 2
2 3
3 4
3 5
```
예상 출력
```
67
```