結果
問題 | No.1333 Squared Sum |
ユーザー |
![]() |
提出日時 | 2021-01-09 17:29:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 484 ms / 2,000 ms |
コード長 | 774 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 147,840 KB |
最終ジャッジ日時 | 2024-11-18 07:30:09 |
合計ジャッジ時間 | 16,554 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
n = int(input())g = [[] for _ in range(n)]for i in range(n-1):a,b,c = [int(i) for i in input().split()]g[a-1].append((b-1,c))g[b-1].append((a-1,c))q = [0]parent = [-1]*ndist = [0]*nfor v in q:for c,wt in g[v]:if c != parent[v]:q.append(c)parent[c] = vdist[c] = wtsum1 = [0]*nsum2 = [0]*ncnt = [1]*nMOD = 10**9+7ans = 0for v in q[::-1]:if v==0: continued = dist[v]sum2[v] += 2*d*sum1[v]+(d**2)%MOD*cnt[v]sum2[v] %= MODsum1[v] += d*cnt[v]sum1[v] %= MODp = parent[v]ans += cnt[p]*sum2[v] + cnt[v]*sum2[p] + 2*sum1[v]*sum1[p]ans %= MODcnt[p] += cnt[v]sum1[p] += sum1[v]sum1[p] %= MODsum2[p] += sum2[v]sum2[p] %= MODprint(ans)