P8821 [CTT Mutual Test 2022] Heavy-Light Decomposition

Please note: **This problem is not a heavy-light decomposition template problem**.

You are given a tree $T$ with $n$ nodes and $m$ **distinct** paths on the tree $I_i = (u_i, v_i)(u_i\neq v_i)$. Specifically, $I_i$ represents the set of all nodes on the simple path between $u_i$ and $v_i$ on the tree. Consider a path on $T$, $I = (u, v)$. Define $f(I) = \sum\limits_{i = 1} ^ m\sum\limits_{j = 1} ^ m [I_i\cup I = I_j\cup I]$. For all distinct paths $I$ on $T$, find the sum of $f(I)$, and take the answer modulo $998244353$. That is, you need to compute $\left(\sum\limits_{u = 1} ^ n\sum\limits_{v = u} ^ n f((u, v))\right) \bmod 998244353$.

The first line contains an integer $S$, indicating the subtask ID. In the sample, the subtask ID is $-1$. The second line contains two integers $n, m$, representing the size of the tree and the number of paths. The next $n - 1$ lines each contain two integers $x_i, y_i$, representing an edge of $T$. The next $m$ lines each contain two integers $u_i, v_i$, representing the $i$-th path $I_i$. **It is guaranteed that all given paths are pairwise distinct**.

Output one line with one integer, the answer.

This problem uses bundled testdata, with a total of $25$ subtasks, numbered $0\sim 24$. **Note that the evaluated subtask ID equals the actual subtask ID $+1$**. The remainder of the subtask ID modulo $5$ classifies subtasks by data size. - If the subtask ID modulo $5$ is $0$, then $n, m\leq 100$, denoted as A1. - If the subtask ID modulo $5$ is $1$, then $n, m\leq 500$, denoted as B1. Depends on A1. - If the subtask ID modulo $5$ is $2$, then $n, m\leq 1557$, denoted as C1. Depends on B1. - If the subtask ID modulo $5$ is $3$, then $n, m\leq 85500$, denoted as D1. Depends on C1. - If the subtask ID modulo $5$ is $4$, then $n, m\leq 2\times 10 ^ 5$, denoted as E1. Depends on D1. The quotient of the subtask ID divided by $5$ classifies subtasks by special constraints. - If the quotient is $0$, then $T$ is a chain, denoted as A2. - If the quotient is $1$, then $T$ is a star, denoted as B2. - If the quotient is $2$, then all path endpoints are pairwise distinct, denoted as C2. - If the quotient is $3$, then all paths share one common endpoint, denoted as D2. - If the quotient is $4$, then there are no special constraints, denoted as E2. Depends on A2, B2, C2, D2. ## Constraints For $100\%$ of the data, $2\leq n\leq 2\times 10 ^ 5$, $1\leq m\leq \min(\frac {n(n - 1)} 2, 2\times 10 ^ 5)$, $1\leq u_i, v_i, x_i, y_i\leq n$, and all $(x_i, y_i)$ form a tree, all $I_i = (u_i, v_i)$ are pairwise distinct, and $u_i\neq v_i$. The scores of each subtask are shown in the following table. | **Score** | **A1** | **B1** | **C1** | **D1** | **E1** | **Total** | | :------: | :----: | :----: | :----: | :----: | :----: | :------: | | **A2** | $1$ | $2$ | $3$ | $7$ | $7$ | $20$ | | **B2** | $1$ | $2$ | $3$ | $4$ | $4$ | $14$ | | **C2** | $1$ | $2$ | $5$ | $7$ | $7$ | $22$ | | **D2** | $1$ | $3$ | $5$ | $4$ | $5$ | $18$ | | **E2** | $2$ | $3$ | $3$ | $9$ | $9$ | $26$ | | **Total** | $6$ | $12$ | $19$ | $31$ | $32$ | $100$ | **Note: Luogu evaluation has no subtask dependencies**. Source: 2022 CTT Mutual Test Round 4. Problem setter: Alex_Wei. Translated by ChatGPT 5