\(P=998244353\) とします．

次のような木を考え，これを \(G\) とおくことにします．

• 入力の木の各辺の中心に新しい頂点を作る． 以後，もともとあった番号 \(i\) の頂点を \(v(i)\)，辺 \(i\) から新しく作った頂点を \(e(i)\) で表す． つまり，頂点 \(e(i)\) は \(v(A_i),v(B_i)\) と隣接するようになる．

• 更に，各頂点 \(e(i)\) に対し，そこから伸びる葉を \(P-1\) 個付け足す．

ここで，有理数 \(w(G)\) を次のように定義してみます．

• \(G\) の各頂点に \([0,1]\) から一様ランダムに選んだ実数を書き込む． 「すべての頂点 \(e(i)\) について，\(e(i)\) に書かれた値が，それに隣接するどの頂点に書かれた値よりも大きい」確率はいくらか？

ここで，\(f(T) \equiv w(G) \mod{P}\) です． これは帰納法によって確認できます．

まず \(N=1\) のケースは明らかです． 次に \(N \geq 2\) のケースを考えます． \(w(G)\) を計算するとき，最大の値が書かれた頂点がどこになるかで分類することを考えます． 頂点 \(e(i)\) に書かれた値が最大になる場合を考えると，これは，\(f(T)\) の計算において，辺 \(i\) を切ることに対応することがわかります． \(w(G)\) の計算では \(1/(N+(N-1)P)\) という係数が登場し，\(f(T)\) の計算では \(1/N\) という係数が登場しますが，これらは \(\text{mod}\ P\) で合同なので，\(w(G)\equiv f(T)\) が従います．

以上より，あとは \(w(G)\) を計算できればよいです． まず，\(G\) 根付き木にしておきます． 根は例えば \(v(1)\) だとします． 各辺 \(i\) について，親の頂点が \(A_i\)，子の頂点が \(B_i\) であるとします．

\(w(G)\) を包除原理に使って求めることを考えます． ここでは，「\(e(i)\) に書かれた値が \(v(A_i)\) に書かれた値より大きい」という制約のみを包除原理によって外します． それ以外の制約は常に満たされているものとします．

すると，ある頂点の集合 \(S=\{e(i_1),e(i_2),\cdots\}\) について，「\(e(i) \in S\) に書かれた値が \(v(A_i)\) に書かれた値より小さい」という制約を考えれば良いことになります． 値の大小関係のある辺だけを考えると，\(G\) はいくつかの部分木に分解されます． この時，各部分木に注目すると，根に近い頂点ほど値が大きい，という単純な制約だけが残ることがわかります． 各頂点にランダムな値を書き込んだときにこのような制約を満たす確率は，各頂点 \(v\) について，\(1/(v\) の部分木サイズ\()\) をかけ合わせた値です．

\(S\) 全てについて上記の値を\(w(G)\) を計算するためには，DP をすればよいです． \(dp[v][k]=v\) 以下の部分木を考えた時，\(v\) から大小関係でつながっている頂点の個数が \(k\) 個である場合に対応する値　とすればよいです． この DP は \(O(N^2)\) で計算できます．

よって元の問題も \(O(N^2)\) で解くことができます．

解答例(c++)

おまけ

上記の解法では \(P-1\) 個の頂点を付け足すといった操作を導入しましたが，最終的には \(P\) に依存しないアルゴリズムが導かれ，実際にこのアルゴリズムの実行結果は真に \(f(T)\) と一致します． そして，この正当性は直接証明することができます．