結果

問題 No.2980 Planar Tree 2
ユーザー PNJ
提出日時 2024-12-04 06:37:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,163 ms / 2,000 ms
コード長 1,376 bytes
コンパイル時間 3,639 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 171,536 KB
最終ジャッジ日時 2025-06-20 11:24:42
合計ジャッジ時間 16,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

n = 10 ** 6
inv = [1 for j in range(n + 1)]
for a in range(2,n + 1):
  # ax + py = 1 <=> rx + p(-x-qy) = -q => x = -(inv[r]) * (p//a)  (r = p % a)
  res = (mod - inv[mod % a]) * (mod // a)
  inv[a] = res % mod

fact = [1 for i in range(n + 1)]
for i in range(1,n + 1):
  fact[i] = fact[i - 1] * i % mod

fact_inv = [1 for i in range(n + 1)]
fact_inv[-1] = pow(fact[-1],mod - 2,mod)
for i in range(n,0,-1):
  fact_inv[i - 1] = fact_inv[i] * i % mod

def binom(n,r):
  if n < r or n < 0 or r < 0:
    return 0
  res = fact_inv[n - r] * fact_inv[r] % mod
  res *= fact[n]
  res %= mod
  return res

N = int(input())
G = [[] for u in range(N)]
for i in range(N - 1):
  u, v = map(int, input().split())
  u, v = u - 1, v - 1
  G[u].append(v)
  G[v].append(u)

D = [0 for u in range(N)]
RG = [[] for u in range(N)]
r = 0
stack = [r]
visit = []
while len(stack):
  u = stack.pop()
  visit.append(u)
  for v in G[u]:
    if D[v] > 0:
      continue
    D[u] += 1
    RG[u].append(v)
    stack.append(v)

sub = [0 for u in range(N)]
for u in visit[:-1]:
  for v in RG[u]:
    sub[u] += sub[v] + 1

ans = 1
for u in range(N):
  x = 0
  for v in RG[u]:
    ans = ans * (1 + sub[v]) % mod
    if D[v] == 0:
      x += 1
  res = fact[D[u] - x] * binom(sub[u], x) % mod
  ans = ans * (res * fact[x] % mod) % mod
  
  
ans = ans * pow(fact[N - 1], -1, mod) % mod
print(ans)
0