結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-10-29 21:17:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 479 ms / 2,000 ms |
コード長 | 1,420 bytes |
コンパイル時間 | 563 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 104,448 KB |
最終ジャッジ日時 | 2024-09-14 21:36:42 |
合計ジャッジ時間 | 4,804 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import dequedef bfs():dist = [-1] * Ndist[0] = D[0]depth = [0] * Nq = deque([])q.append(0)while q:cn = q.popleft()for nn in adj_list[cn]:if dist[nn] == -1:parents[0][nn] = cndist[nn] = dist[cn]+D[nn]depth[nn] = depth[cn]+1q.append(nn)return dist, depthdef lca(u, v):if depth[u] > depth[v]:u, v = v, ufor k in range(log_size):if ((depth[v]-depth[u])>>k)&1:v = parents[k][v]if u == v:return ufor k in range(log_size-1, -1, -1):if parents[k][u] != parents[k][v]:u = parents[k][u]v = parents[k][v]return parents[0][u]N = int(input())adj_list = [[] for _ in range(N)]for _ in range(N-1):A, B = map(int, input().split())adj_list[A].append(B)adj_list[B].append(A)D = [int(input()) for _ in range(N)]log_size = N.bit_length()parents = [[-1] * N for _ in range(log_size)]dist, depth = bfs()for i in range(1, log_size):for j in range(N):parents[i][j] = parents[i-1][parents[i-1][j]]M = int(input())ans = 0for _ in range(M):A, B, C = map(int, input().split())L = lca(A, B)ans += (dist[A]+dist[B]-2*dist[L]+D[L])*Cprint(ans)