Number of Trees

Time limit2sMemory limit1024 MB

Summary

For a tree with vertex durabilities, sum the pieces left by each subtree after removing vertices with durability at most j, over all j from 1 to K.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Sorting
Solved: No attempts yet

Problem

Jeonghu: Dong-hyeon, it is a Christmas tree!

Dong-hyeon: Right! Suppose a subtree $T'$ of the tree $T$ rots, and every vertex $i$ with durability $A_i \leq j$ is removed along with its incident edges. Then $T'$ splits into $f_j(T')$ pieces, right? (If everything is removed, $f_j(T')=0$ .)
Jeonghu: Right! For every subtree $T'$ of $T$ , let $g_j(T)$ be the sum of $f_j(T')$ . What is the remainder when $\sum_{j=1}^K g_j(T)$ is divided by $998\,244\,353$ ?
Dong-hyeon: Ah! I think we can solve it in less than $O(N^2)$ .

How would that work? Let's try it ourselves.

Input

The first line contains $N$ and $K$ . The second line contains $A_1, A_2, \cdots, A_N$ . From the third line through line $N+1$ , each line contains $u$ and $v$ , the two vertices joined by an edge of the tree. Every vertex can reach every other vertex through the edges.

Output

Print the remainder of $\sum_{j=1}^K g_j(T)$ divided by $998\,244\,353$ .

Constraints

$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$
All given numbers are integers.

Examples2

Example 1
Input
```
4 3
1 2 1 3
1 2
2 3
2 4
```
Expected output
```
14
```
Example 2
Input
```
5 6
5 3 5 1 2
1 2
2 3
3 4
3 5
```
Expected output
```
67
```