問題一覧 > 通常問題

No.2980 Planar Tree 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : tko919tko919 / テスター : 👑 testestesttestestest
3 ProblemId : 11615 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-12-03 04:47:40

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点の無向木 $T$ が与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。
$T$ の各頂点に対し円周上の点を独立かつ一様ランダムに配置し、それらの点を各辺に対応する線分で結びます。
このとき、どの線分も端点以外で他の線分と共有点を持たない確率を $\bmod\ 998244353$ で求めてください。

厳密には以下の通りです。
各頂点 $v$ についてある $\theta_v \in [0,2\pi)$ を独立かつ一様ランダムに与え、$P_v=(\cos(\theta_v),\sin(\theta_v))$ とします。
そして、辺 $e=(u,v)$ に対し単位円板上で $P_u,P_v$ を結んだ線分を $I_e$とします。
このとき、次の条件をみたす確率を $\bmod\ 998244353$ で求めてください。

  • 任意の相異なる辺 $e,f$ について、線分 $I_e,I_f$ が端点以外で交わらない。
確率 $\bmod\ 998244353$ とは

求める確率は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P,Q$ を用いて ${P \over Q}$ と表したとき、 $R \times Q \equiv P( \bmod\ 998244353)$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

入力

$N$
$u_1\ v_1$
$\vdots$
$u_{N-1}\ v_{N-1}$
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq u_i < v_i \leq N$
  • 入力で与えられるグラフは木
  • 入力は全て整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
1 2
2 3
3 4
出力
665496236

辺 $1$ に対応する弦で円を分断したとき、頂点 $3,4$ に対応する点が同じ側に入っているかつそのときに限り交わりません。
求める確率は $\int_0^1 x^2+(1-x)^2 dx={2 \over 3}$ です。

サンプル2
入力
10
1 7
7 10
8 10
3 8
4 8
9 10
6 9
5 9
2 7
出力
795030324

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。