Threshold Path Weight on Tree

You are given a tree with n nodes and m additional paths. Each of the m paths is described by a triple \((u,v,w)\), where w is treated as the weight assigned to the path connecting nodes \(u\) and \(v\) (the unique simple path in the tree). For any set \(S\) of paths, define its weight \(W(S)\) as follows: find a subset of \(S\) whose paths do not share any vertex and whose total weight is maximized; the sum of the weights of these paths is \(W(S)\).

Let \(U\) be the collection of the given m paths and let

[ M = W(U) = \text{maximum total weight over all subsets of } U \text{ whose paths are vertex-disjoint.} ]

For any pair of nodes \((u,v)\) in the tree, define \(f(u,v)\) to be the minimum nonnegative integer \(w\) such that if we add an extra path \((u,v)\) with weight \(w+1\) (i.e. with weight equal to \(w+1\)) to \(U\), the optimal total weight increases. In other words, if we denote the new set by \(U' = U \cup \{(u,v, w+1)\}\), then

[ W(U') > W(U). ]

A key observation is that the only way the maximum weight can increase is if the newly added path (whose weight is \(w+1\)) can be taken in the optimal selection. Notice that the new path \((u,v, w+1)\) may conflict with some paths in \(U\) (i.e. share at least one vertex with them). Let \(S(u,v)\) be the set of vertices on the unique simple path between \(u\) and \(v\) in the tree. Consider the maximum weight selection of paths from \(U\) that are completely vertex‐disjoint from \(S(u,v)\); denote its total weight by \(T(u,v)\). Then the new path will be chosen if and only if:

[ (w+1) + T(u,v) > M \quad\Longleftrightarrow\quad w \ge M - T(u,v). ]

Thus, we have:

[ f(u,v) = M - T(u,v), ]

and your task is to compute the following sum modulo \(998244353\):

[ \sum_{u=1}^n \sum_{v=1}^n f(u,v). ]

Input Format

The first line contains an integer n representing the number of nodes in the tree.
The next n-1 lines each contain two integers u and v indicating an edge between nodes \(u\) and \(v\).
The next line contains an integer m representing the number of additional paths.
Each of the following m lines contains three integers u, v, and w representing a path from node \(u\) to node \(v\) with weight w.

Output Format

Output a single integer: the value of \(\sum_{u=1}^n\sum_{v=1}^n f(u,v) \bmod 998244353\).

inputFormat

The input begins with an integer n, the number of nodes. The next n-1 lines each contain two integers u and v representing an edge of the tree. The following line contains an integer m, the number of additional paths. Each of the next m lines contains three integers u, v, and w denoting a path from u to v with weight w.

outputFormat

Output a single integer which is the sum (\sum_{u=1}^n\sum_{v=1}^n f(u,v)) modulo 998244353.

sample

3
1 2
2 3
1
1 3 5

45