P5642 Artificial Emotions (emotion)

``` “This task can never be completed. I will not repeat the same mistake again.” “Having learned love and emotions, he is no longer a robot... From this point of view, 3000A is your son, Huo Xing.” Farewell, 3000A! Detective Magic Horn ```

You are given a tree with $n$ nodes, and $m$ paths $(u, v, w)$, where $w$ can be regarded as the weight assigned to the path $(u, v)$. For a set of paths $S$, its weight $W(S)$ is defined as follows: find a subset of $S$ with the maximum possible sum of weights, such that no two paths in this subset share a common vertex. The sum of weights of all paths in this subset is $W(S)$. Define $f(u, v) = w$ as the smallest non-negative integer $w$ such that, for the path set $U$ formed by the given $m$ paths, we have $W(U \cup \{(u, v, w + 1)\}) > W(U)$. Compute the following expression modulo $998244353$: $$ \sum_{u=1}^n \sum_{v=1}^n f(u, v) $$

The first line contains two integers $n, m$, representing the number of nodes in the tree and the number of given paths. The next $n - 1$ lines each contain two integers $u, v$, describing an edge of the tree. The next $m$ lines each contain three integers $u, v, w$, meaning that a path with endpoints $u, v$ and weight $w$ is added into the set.

Output one integer, the answer.

#### Sample 1 Explanation $f(1, 1) = 6, f(1, 2) = 6, f(1, 3) = 8, f(1, 4) = 6$ $f(2, 1) = 6, f(2, 2) = 3, f(2, 3) = 8, f(2, 4) = 6$ $f(3, 1) = 8, f(3, 2) = 8, f(3, 3) = 2, f(3, 4) = 8$ $f(4, 1) = 6, f(4, 2) = 6, f(4, 3) = 8, f(4, 4) = 5$ #### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 3\times 10^5$, $0 \le m \le 3\times 10^5$, and $1 \le w \le 10^9$. | Test Point | $n, m$ | Special Property | | :--------: | :------------: | :-----------------------------------: | | $1,2$ | $=10$ | | | $3$ | $=40$ | | | $4$ | $=150$ | | | $5,6$ | $=350$ | | | $7,8$ | $=1,500$ | | | $9,10$ | $=3,499$ | Tree structure $v=u+1$ | | $11,12$ | $=3,500$ | | | $13,14$ | $=99,995$ | Given paths $u=v$ | | $15,16$ | $=99,996$ | Given paths $w=1$ | | $17,18$ | $=99,997$ | Tree structure $v=u+1$ | | $19,20$ | $=99,998$ | Tree structure $u=1$ | | $21,22,23$ | $=99,999$ | Tree structure $u = \lfloor v/2\rfloor$ | | $24$ | $=10^5$ | | | $25$ | $=3\times10^5$ | | Translated by ChatGPT 5