結果
問題 | No.1207 グラフX |
ユーザー |
|
提出日時 | 2020-08-30 14:44:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,437 ms / 2,000 ms |
コード長 | 1,556 bytes |
コンパイル時間 | 353 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 347,520 KB |
最終ジャッジ日時 | 2024-12-16 03:28:51 |
合計ジャッジ時間 | 39,467 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import sysinput = lambda : sys.stdin.readline().rstrip()sys.setrecursionlimit(max(1000, 10**9))write = lambda x: sys.stdout.write(x+"\n")# inputnan,m,X = list(map(int, input().split()))M = 10**9+7xyz = [list(map(int, input().split())) for _ in range(m)]for i in range(m):xyz[i] = (xyz[i][0]-1, xyz[i][1]-1, xyz[i][2])xyz.sort(key=lambda x: x[2])class UnionFindTree:def __init__(self, n):self.n = nself.parent = list(range(n))self.size = [1] * ndef root(self, i):inter = set()while self.parent[i]!=i:inter.add(i)i = self.parent[i]r = ifor i in inter:self.parent[i] = rreturn rdef connect(self, i, j):ri = self.root(i)rj = self.root(j)if ri==rj:returnif self.size[ri]<self.size[rj]:self.parent[ri] = rjself.size[rj] += self.size[ri]else:self.parent[rj] = riself.size[ri] += self.size[rj]ans = 0uf = UnionFindTree(n)ss = [0] * nes = [[] for _ in range(n)]for x,y,z in xyz:rx = uf.root(x)ry = uf.root(y)if rx==ry:continueuf.connect(x,y)es[x].append((y,z))es[y].append((x,z))ans = 0size = [None]*nstart = 0def sub(u, p):global ansres = 0for v,z in es[u]:if v==p:continuesize = sub(v,u)res += sizeans = ans + size * (n-size) * pow(X,z,M)ans %= Mreturn res+1sub(0,-1)print(ans%M)