結果
問題 | No.1333 Squared Sum |
ユーザー | tpyneriver |
提出日時 | 2020-10-31 07:41:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,214 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 163,300 KB |
最終ジャッジ日時 | 2024-07-22 04:41:03 |
合計ジャッジ時間 | 57,870 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 TLE * 15 |
ソースコード
import sys readline = sys.stdin.readline def decomposition(Edge, st = 0): N = len(Edge) bfsorder = [st] for i in range(N): vn = bfsorder[i] for vf in Edge[vn]: Edge[vf].remove(vn) bfsorder.extend(Edge[vn]) sset = [0]*N for vn in bfsorder[::-1]: se = st = 0 for vf in Edge[vn]: st |= sset[vf]&se se |= sset[vf] tmp = ~se & -(1<<st.bit_length()) l = -tmp & tmp sset[vn] = (se|l) & -l return [(-l&l).bit_length()-1 for l in sset] MOD = 10**9+7 N = int(readline()) Edge = [[] for _ in range(N)] for _ in range(N-1): u, v, w = map(int, readline().split()) u -= 1 v -= 1 Edge[u].append((v, w)) Edge[v].append((u, w)) levels = decomposition([[e[0] for e in ei] for ei in Edge]) ans = 0 size = [0]*N ds = [0]*N ds2 = [0]*N dist = [0]*N color = [0]*N for lv in range(max(levels), 0, -1): used = [0]*N for i in range(N): if levels[i] > lv: used[i] = 1 for vn in range(N): if levels[vn] != lv: continue used[vn] = 1 dsum = 0 ssum = 0 stack = [] for vf, w in Edge[vn]: if used[vf]: continue color[vf] = vf ssum += 1 size[vf] = 1 used[vf] = 1 dist[vf] = w dsum = (dsum + w)%MOD ds[vf] = w ds2[vf]= w*w%MOD stack.append(vf) cs = stack[:] while stack: vn = stack.pop() for vf, w in Edge[vn]: if used[vf]: continue used[vf] = 1 c = color[vn] color[vf] = c dist[vf] = (dist[vn] + w)%MOD ds[c] = (ds[c] + dist[vf])%MOD dsum = (dsum + dist[vf])%MOD ds2[c] = (ds2[c] + dist[vf]*dist[vf])%MOD size[c] += 1 ssum += 1 stack.append(vf) ans = (ans + dsum*dsum)%MOD for r in cs: ans = (ans + ds2[r] + (ssum-size[r])*ds2[r] - ds[r]*ds[r])%MOD print(ans)