結果
問題 | No.758 VVVVV |
ユーザー |
![]() |
提出日時 | 2020-08-27 21:51:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 1,495 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 96,640 KB |
最終ジャッジ日時 | 2024-11-08 09:50:41 |
合計ジャッジ時間 | 5,393 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import sys; input = sys.stdin.buffer.readlinesys.setrecursionlimit(10**7)from collections import defaultdictcon = 10 ** 9 + 7; INF = float("inf")def getlist():return list(map(int, input().split()))class Combination(object):def __init__(self, N, con):self.fac = [0] * (N + 1)self.inv = [0] * (N + 1)self.finv = [0] * (N + 1)self.fac[0], self.fac[1] = 1, 1self.inv[1] = 1self.finv[0], self.finv[1] = 1, 1for i in range(2, N + 1):self.fac[i] = self.fac[i - 1] * i % conself.inv[i] = self.inv[con % i] * (con - (con // i)) % conself.finv[i] = self.finv[i - 1] * self.inv[i] % condef com(self, N, k):return (self.fac[N] * self.finv[k] * self.finv[N - k]) % conclass Graph(object):def __init__(self):self.graph = defaultdict(list)def __len__(self):return len(self.graph)def add_edge(self, a, b):self.graph[a].append(b)def DFS(G, W, visit, node):for i in G.graph[node]:if visit[i] != 1:visit[i] = 1DFS(G, W, visit, i)W[node] += W[i]#処理内容def main():N = int(input())G = Graph()for i in range(N - 1):a, b = getlist()a -= 1; b -= 1G.add_edge(a, b)G.add_edge(b, a)W = [1] * Nvisit = [0] * Nvisit[0] = 1DFS(G, W, visit, 0)#部分木 大きさleaf_cnt = 0for i in W:if i == 1:leaf_cnt += 1C = Combination(N, con)ans = C.com(N - 1, leaf_cnt - 1) * C.com(N - 2, leaf_cnt - 1) * pow(leaf_cnt, con - 2, con)ans %= conprint(ans)if __name__ == '__main__':main()