結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2022-01-03 19:25:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 880 ms / 2,000 ms |
コード長 | 3,807 bytes |
コンパイル時間 | 143 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 193,408 KB |
最終ジャッジ日時 | 2024-10-13 07:07:56 |
合計ジャッジ時間 | 6,201 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
import syssys.setrecursionlimit(10**6)class LCA():def __init__(self,e,root=0):self.N = len(e)self.e = eself.root = rootself.IN = [-1]*Nself.OUT = [-1]*Nself.DIST = [-1]*Nself.time = 0self.DIST[root] = 0self.parents = [-1]*Nself.dfs(root)self.depth = [(self.DIST[i],i) for i in range(N)]self.init_val = [-1]*(2*N)for i in range(N):x = self.IN[i]y = self.OUT[i]self.init_val[x] = self.depth[i]self.init_val[y] = self.depth[self.parents[i]]self.T = self.SegTree(self.init_val)def dfs(self,x):self.IN[x] = self.timeself.time += 1for ix in e[x]:if self.DIST[ix] != -1:continueself.parents[ix] = xself.DIST[ix] = self.DIST[x] + 1self.dfs(ix)self.OUT[x] = self.timeself.time += 1def lca(self,l,r):L = self.IN[l]R = self.IN[r]if R<L:L,R = R,LR += 1return self.T.query(L,R)[1]def distance_between(self,l,r):p = self.lca(l,r)return self.DIST[l]+ self.DIST[r] - 2*self.DIST[p]def distance_from_root(self,x):return self.DIST[x]class SegTree:"""Segment Tree"""def __init__(self, init_val, segfunc = None, ide_ele= None):"""初期化init_val: 配列の初期値"""if segfunc is None:def segfunc(x,y):return min(x,y)ide_ele = (float('inf'),-1)n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.num# 配列の値を葉にセットfor i in range(n):self.tree[self.num + i] = init_val[i]# 構築していくfor i in range(self.num - 1, 0, -1):self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):"""k番目の値をxに更新k: index(0-index)x: update value"""k += self.numself.tree[k] = xwhile k > 1:self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])k >>= 1def query(self, l, r):"""[l, r)のsegfuncしたものを得るl: index(0-index)r: index(0-index)"""res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:res = self.segfunc(res, self.tree[r - 1])l >>= 1r >>= 1return resN = int(input())e = [[] for _ in range(N)]for _ in range(N-1):a,b = map(int,input().split())e[a].append(b)e[b].append(a)U = [int(input()) for _ in range(N)]W = [-1]*NtW = 0def dfs(x):global tWtW += U[x]W[x] = tWfor ix in e[x]:if W[ix] != -1:continuedfs(ix)tW -= U[x]dfs(0)L = LCA(e)ans = 0M = int(input())for _ in range(M):a,b,c = map(int,input().split())p = L.lca(a,b)ans += c*(W[a] + W[b] - 2*W[p] + U[p])print(ans)