#1029885 (PyPy3) No.2980 Planar Tree 2

• 問題: No.2980 Planar Tree 2
• ユーザー: PNJ
• 提出日時: 2024-12-04 06:37:53
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 789 ms / 2,000 ms
• コード長: 1,376 bytes
• コンパイル時間: 397 ms
• コンパイル使用メモリ: 82,560 KB
• 実行使用メモリ: 181,308 KB
• 最終ジャッジ日時: 2024-12-04 06:38:11
• 合計ジャッジ時間: 17,358 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX