from types import GeneratorType from collections import defaultdict def bootstrap(f, stack=[]): def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc class AuxiliaryTree: def __init__(self, N, G): self.N = N self.G = G self.IN = [0]*N self.OUT = [0]*N self.depth = [0]*N self.depth2 = [0]*N self.E = [] self.dfs(0, -1, 0, 0) self.L = len(self.E) self.lg = [0]*(self.L+1) self.make_sparse_table() @bootstrap def dfs(self, n, p, d, d2): self.depth[n] = d self.depth2[n] = d2 self.IN[n] = len(self.E) self.E.append(n) for v, w in self.G[n]: if v == p: continue yield self.dfs(v, n, d+1, d2+w) self.E.append(n) self.OUT[n] = len(self.E) self.E.append(n) yield def make_sparse_table(self): for i in range(2, self.L+1): self.lg[i] = self.lg[i>>1]+1 self.st = [[self.L]*(self.L-(1<