P7422 "PMOI-2" Cities

Country $P$ has $N$ cities and $M$ undirected roads. City $1$ is the capital, and any two cities can reach each other through roads. Now Country $P$ is going to hold ION in the capital. To build the contest venue, each city needs to provide raw materials to the capital. City $i$ can provide raw material of type $c_i$. Each city will have a truck departing from that city and going to the capital **along a simple path**. If the truck starting from city $A$ must pass through city $B$, then we say that city $B$ lies on the unavoidable path from city $A$ to the capital. If for cities $A, B, C$, **any simple path** from $B$ to $A$ and **any simple path** from $C$ to $A$ have no common edges, then we say that cities $B$ and $C$ are independent of each other with respect to city $A$. Let $f(A,k)$ be the number of $k$-element sets $\{B_1,B_2,\cdots B_k\}$ that satisfy all of the following conditions: 1. For any $1 \le i \le k$ with $A \neq B_i$, **city $A$ lies on the unavoidable path from city $B_i$ to the capital**, and the material supplied by city $B_i$ is **different** from that of city $A$. 2. For any $1 \le i < j \le k$, **$B_i$ and $B_j$ are independent with respect to $A$**, and the raw materials supplied by $B_i$ and $B_j$ are **the same**. Define the attractiveness of holding ION as $\sum_{i=1}^N \sum_{k=1}^K f(i,k)$, where $K$ is a given constant. Now, as the leader of Country $P$, you want to know the attractiveness of this ION. **Since the answer may be very large, please output the answer modulo $998244353$.**

The first line contains three integers $N, M, K$. The second line contains $N$ integers. The $i$-th number is the type of raw material $c_i$ supplied by city $i$. The next $M$ lines each contain two integers $u, v$, indicating a road in Country $P$. It is guaranteed that there are **no multiple edges and no self-loops**. ($1 \le u, v \le N, u \neq v$)

Output one integer, the answer.

[Sample Explanation] In the sample, the map of Country $P$ is as follows:  In the table below, the entry in row $i$ and column $j$ represents $f(i,j)$. | $4$ | $0$ | $0$ | $0$ | | -----------: | -----------: | -----------: | -----------: | $4$ | $0$ | $0$ | $0$ | | $2$ | $1$ | $0$ | $0$ | | $1$ | $0$ | $0$ | $0$ | So the attractiveness is $4 + 4 + 2 + 1 + 1 = 12$. [Constraints] **This problem uses bundled testdata**. - Subtask 1 (10 pts): $N, K \le 8$. - Subtask 2 (10 pts): $K = 1$. - Subtask 3 (15 pts): $K = 2$. - Subtask 4 (15 pts): the graph is guaranteed to be a tree. - Subtask 5 (15 pts): $N \le 2000$. - Subtask 6 (15 pts): $N \le 4 \times 10^4$. - Subtask 7 (20 pts): no special constraints. For $100\%$ of the data: $1 \le N \le 5 \times 10^5$, $1 \le M \le \min\left(10^6, \frac{N \times (N - 1)}{2}\right)$, $1 \le K \le 20$, $1 \le c_i \le 10^9$. **Warm reminder**: The input is large, so please use a fast input method. Translated by ChatGPT 5