Let \(P=998244353\).

Let \(G\) be the tree made as follows:

• Make a new vertex at the center of each edge in the given tree. Below, let \(v(i)\) denote the original vertex numbered \(i\), and \(e(i)\) denote the new vertex on Edge \(i\). That is, Vertex \(e(i)\) will be adjacent to \(v(A_i)\) and \(v(B_i)\).

• Furthermore, attach \(P-1\) new leaves to each vertex \(e(i)\).

Now, let us define a rational number \(w(G)\) as follows.

• On each vertex in \(G\), let us write a real number chosen uniformly at random from \([0,1]\). What is the probability that the following holds: for every vertex \(e(i)\), the value written on \(e(i)\) is greater than the values written on all adjacent vertices?

Here, we have \(f(T) \equiv w(G) \mod{P}\), which can be verified by induction.

The case \(N=1\) is trivial, so consider the case \(N \geq 2\). In the computation of \(w(G)\), let us do classification according to which of the vertices has the greatest value written on it. It can be seen that the situation where Vertex \(e(i)\) has the greatest value corresponds to cutting Edge \(i\) in the computation of \(f(T)\). There is a coefficient \(1/(N+(N-1)P)\) in the computation of \(w(G)\), and a coefficient \(1/N\) in the computation of \(f(T)\), but they are congruent \(\text{mod}\ P\), so it follows that \(w(G)\equiv f(T)\).

Therefore, what remains is to compute \(w(G)\). First, we root \(G\) at some arbitrary vertex, say \(v(1)\). For each edge \(i\), let Vertex \(A_i\) be the parent of Vertex \(B_i\).

Let us try to find \(w(G)\) using the inclusion-exclusion principle. Here, we use it only to drop the restriction that each \(e(i)\) has a value greater than that of \(v(A_i)\), and assume that all other restrictions are satisfied.

Then, we are to consider, for a set of vertices \(S=\{e(i_1),e(i_2),\cdots\}\), the restriction that each \(e(i) \in S\) has a value smaller than that of \(v(A_i)\). If we consider only those edges with magnitude relations, \(G\) will be divided into some subtrees. Here, the restrictions in each subtree are rather simple: the closer to the root, the greater the value must be. The probability that such restrictions are satisfied when writing a random value on each vertex is the product of \(1/(\)the number of vertices below \(v)\) over all vertices \(v\) in the subtree.

To consider all \(S\) to compute \(w(G)\), one can use DP. Here, let \(dp[v][k]=(\)the sum of values corresponding to the cases when there are \(k\) vertices connected to \(v\) by magnitude relations\()\). This DP takes \(O(N^2)\) time.

Therefore, the original problem can also be solved in \(O(N^2)\) time.

Sample code (c++)

P.S.

In the solution above, we introduced modifications to the graphs, such as adding \(P-1\) leaves. However, one can eventually derive an algorithm that does not depend on \(P\) and returns exactly \(f(T)\). Additionally, one can directly prove its validity.