Probabilistic Tree Weight Distribution

We are given a rooted tree with n nodes (node 1 is the root) where each node has at most two children. For each node x, its weight is defined as follows:

• If x is a leaf (has no children), its weight is given as input. It is guaranteed that the weights for all leaves are distinct.
• If x is an internal node (has one or two children), then with probability \(p_x\) its weight equals the maximum of its children’s weights, and with probability \(1-p_x\) it equals the minimum of its children’s weights. Note that if a node has only one child then the maximum and minimum are equal, so the probability does not affect the outcome.

Suppose that the weight of the root (node 1) can take m possible values. Let these values in increasing order be \(V_1, V_2,\dots,V_m\) and their corresponding probabilities be \(D_1, D_2,\dots,D_m\) (with each \(D_i>0\)). You are to compute:

[ \sum_{i=1}^{m} i \cdot V_i \cdot D_i^2 ]

Output the answer modulo 998244353.

inputFormat

The input is given as follows:

1. The first line contains an integer n (the number of nodes).
2. The next n-1 lines each contain two integers u and v, which indicates that there is an edge from node u (the parent) to node v (the child). It is guaranteed that the tree is rooted at node 1 and every node has at most two children.
3. The following n lines describe the nodes in order from 1 to n. Each line is one of the following formats:
   • L w — indicates that the node is a leaf with given weight w (an integer).
   • I p — indicates that the node is internal and p is the probability (given as a fraction in the form a/b) that the node takes the maximum of its children’s weights.

outputFormat

Output a single integer, the value of \(\sum_{i=1}^{m} i \cdot V_i \cdot D_i^2\) modulo 998244353.

sample

3
1 2
1 3
I 1/2
L 3
L 5

749683268