結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2022-10-15 20:05:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 744 ms / 2,000 ms |
コード長 | 1,304 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 109,336 KB |
最終ジャッジ日時 | 2024-06-26 20:16:30 |
合計ジャッジ時間 | 5,945 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
from collections import dequen = int(input())g = [[] for _ in range(n)]for _ in range(n - 1):a, b = map(int, input().split())g[a].append(b)g[b].append(a)u = [int(input()) for _ in range(n)]src = 0depth = [None for _ in range(n)]depth[src] = 0dq = deque()dq.appendleft(src)k = n.bit_length()doub = [[None for _ in range(n)] for _ in range(k)]doub[0][src] = srccost = [0 for _ in range(n)]cost[src] = u[src]while len(dq) > 0:cur = dq.pop()for nxt in g[cur]:if not depth[nxt] is None:continuedepth[nxt] = depth[cur] + 1cost[nxt] = cost[cur] + u[nxt]doub[0][nxt] = curdq.appendleft(nxt)for i in range(1, k):for v in range(n):doub[i][v] = doub[i - 1][doub[i - 1][v]]def lca(u, v):ut = uvt = vif depth[ut] > depth[vt]:ut, vt = vt, utdiff = depth[vt] - depth[ut]for i in range(k):if (diff >> i) & 1 != 0:vt = doub[i][vt]if ut != vt:for i in range(depth[ut].bit_length() - 1, -1, -1):if doub[i][ut] != doub[i][vt]:ut = doub[i][ut]vt = doub[i][vt]if ut != vt:ut = doub[0][ut]return utans = 0m = int(input())for _ in range(m):a, b, c = map(int, input().split())l = lca(a, b)ans += c * (cost[a] + cost[b] - 2 * cost[l] + u[l])print(ans)