import sequtils,bitops template times*(n:int,body) = (for _ in 0.. self.depth[v] : swap(u,v) for k in 0.." .} 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 E = E.deleteParent() let lca = E.initLowestCommonAnsestor() 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 E[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.find(u,v) ans += (C0[u] + C0[v] - 2 * C0[parent] + C[parent]) * c echo ans