import sequtils template times*(n:int,body) = (for _ in 0..= 0: traces[src] = @[values[src]] parents[src] = @[pre] for dst in E[src]: if dst != pre : trace1(dst,src,rank+1) trace1(root,-1,0) for i in 1..<1e12.int: var dirty = false for src in 0..= parents[src].len: continue let mid = parents[src][i-1] if i-1 >= parents[mid].len: continue parents[src].add parents[mid][i-1] traces[src].add apply(traces[src][i-1],traces[mid][i-1]) dirty = true if not dirty : break result.n = n result.root = root result.ranks = ranks result.values = values result.traces = traces result.parents = parents result.apply = apply result.init = init proc trace[T](self:DoublingTree[T],u,v:int):T = if u == v : return self.init(u,self.ranks[u]) var u = u var v = v # rankを揃える. if self.ranks[u] < self.ranks[v]: swap(u,v) let s1 = u let s2 = v result = self.init(v,self.ranks[v]) while self.ranks[u] != self.ranks[v]: for pi in (self.parents[u].len-1).countdown(0): let parent = self.parents[u][pi] if self.ranks[parent] >= self.ranks[v]: result = self.apply(result,self.traces[u][pi]) u = parent break var s3 = u if u != s2: result = self.apply(result,self.init(u,self.ranks[u])) while u != v : u = self.parents[u][0] v = self.parents[v][0] if u == v : break result = self.apply(result,self.traces[u][0]) result = self.apply(result,self.traces[v][0]) for i in (self.parents[u].len-1)..0: if self.parents[u][i] == self.parents[v][i]: continue result = self.apply(result,self.traces[u][i]) result = self.apply(result,self.traces[v][i]) u = self.parents[u][i] v = self.parents[v][i] if u != s1 and u != s2 and u != s3: result = self.apply(result,self.init(u,self.ranks[u])) # 最小共通祖先(LCA) with ダブリング # 祖先のindexとそのrankが得られる. type IndexAndRank = tuple[i,rank:int] proc LCA(E:seq[seq[int]],root:int = 0) : DoublingTree[IndexAndRank] = # パス上でrankが低いものを保持. E.newDoublingTree(root ,proc(x,y:IndexAndRank):IndexAndRank = if x.rank < y.rank: return x return y ,proc(i,rank:int):IndexAndRank = (i,rank) ) proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "" .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord # 木を造って根からの距離を保持してLCA分引く let n = scan() var E = newSeqWith(n,newSeq[int]()) (n-1).times: let u = scan() let v = scan() E[u] &= v E[v] &= u let lca = E.LCA(0) let ER = E.toRootedTree(0) let C = newSeqWith(n,scan()) # cost var C0 = newSeqWith(n,-1) # 0 からのcost proc fillFrom0(i,c:int) = C0[i] = C[i] + c for dst in ER[i]: fillFrom0(dst,C0[i]) fillFrom0(0,0) var ans = 0 scan().times: let u = scan() let v = scan() let c = scan() let parent = lca.trace(u,v).i ans += (C0[u] + C0[v] - 2 * C0[parent] + C[parent]) * c echo ans