小Hはゲームをプレイしています。
このゲームは都市を建設するゲームで、ゲーム内には $n$ 個の都市が存在します。
都市間の通信を可能にするため、小Hは $n-1$ 本の辺を用いて都市を接続しました。辺 $(x, y)$ は都市 $x$ と都市 $y$ が直接通信できることを保証します。これらの辺を通じて、任意の2つの都市は直接的または間接的に通信可能です。
上記の構成には問題があることがわかります。2つの都市間において、経由する中継地点が多いほど、メッセージの送信にかかる時間が長くなります。その結果、通信が便利な都市と不便な都市が生じてしまいます。
しかし、辺の数を増やすと小Hが管理しきれなくなるという問題が発生します。この矛盾を解決するため、小Hは一定時間ごとにネットワークをランダムに再構築するという方法を考え出しました。これにより、任意の2都市間の通信時間の期待値が等しくなります。
ただし、ネットワークの再構築にはコストがかかります。元のネットワークを $T_1$、新しいネットワークを $T_2$ とし、2つのネットワークで共通する辺の数を $x$ 本とすると、小Hは調整時にこれらの辺を無視できます。
当然、無視できる辺が多いほど良いため、小Hはこのスキームの価値を $x \cdot 2^x$ と定義しました。
今、小Hは最初のネットワーク再構築を行おうとしています。すべての可能なスキームの価値の合計はいくらになるでしょうか。
答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを求めてください。
問題の形式化
頂点集合 $V$、辺集合 $E_1$ からなる木 $T_1=\{V, E_1\}$ が与えられます ($|V|=n$)。頂点集合 $V$ で構成可能な全域木の集合を $S$ とするとき、以下を計算してください。
$$\left(\sum_{T_2\in S} |E_1\cap E_2|\cdot 2^{|E_1\cap E_2 |}\right) \bmod 998244353 $$
なお、$|S|=n^{n-2}$ であることは既知とします。
入力形式
1行目に整数 $n$ が与えられます。
続く $n-1$ 行には、それぞれ2つの整数 $x_i, y_i$ が与えられ、$T_1$ の辺を表します。
出力形式
価値の合計を $998244353$ で割った余りを1行で出力してください。
入出力例
入力 1
4 1 2 2 3 3 4
出力 1
94
注記
3本の辺を含む全域木は1種類のみです。したがって、寄与は $3 \times 2^3 = 24$ です。
2本の辺を含む全域木について場合分けします。$(1, 2)$ または $(3, 4)$ を含まない場合、それぞれ2通りずつ存在します。$(2, 3)$ を含まない場合、3通り存在します。したがって、寄与は $7 \times 2 \times 2^2 = 56$ です。
1本の辺を含む全域木について、$(1, 2)$ または $(3, 4)$ を選ぶ場合、それぞれ2通りずつ存在します。$(2, 3)$ を選ぶ場合、3通り存在します。したがって、寄与は $7 \times 2 = 14$ です。
答えは $24 + 56 + 14 = 94$ となります。
サブタスク
本問題はサブタスク制です。
すべてのデータにおいて、$1 \le n \le 2\times 10^6$ を満たします。
サブタスクは以下の通りです。
| サブタスク番号 | $n$ | 特殊条件 | 配点 |
|---|---|---|---|
| $1$ | $\le 80$ | なし | $5$ |
| $2$ | $\le 300$ | なし | $5$ |
| $3$ | $\le 3000$ | 特殊条件 A | $5$ |
| $4$ | $\le 3000$ | 特殊条件 B | $5$ |
| $5$ | $\le 3000$ | なし | $10$ |
| $6$ | $\le 10^5$ | 特殊条件 A | $10$ |
| $7$ | $\le 10^5$ | 特殊条件 B | $10$ |
| $8$ | $\le 2\times 10^6$ | 特殊条件 A | $10$ |
| $9$ | $\le 2\times 10^6$ | 特殊条件 B | $10$ |
| $10$ | $\le 2\times 10^6$ | なし | $30$ |
表中の特殊条件は以下の通りです。
- 特殊条件 A：グラフはパスグラフ（鎖状）である。
- 特殊条件 B：グラフはスターグラフ（菊花状）である。
ヒント
本問題は入出力のデータ量が大きいため、高速な読み込み方法を使用してください。