import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline class HLDecomposition: def __init__(self, N, G, op, e): self.N = N self.G = G self.op = op self.e = e self.parent = [-1]*N self.depth = [0]*N self.size = [0]*N self.heavy = [-1]*N self.__build_1(0) self.top = [0]*N self.HLD_G = [0] self.__build_2(0) self.HLD_G = self.HLD_G[::-1] self.node_w = [self.e.copy() for _ in range(N)] self.node = [N-1]*N self.__make_tree() def set(self, v, w, weight): if self.parent[w]==v: v, w = w, v elif self.parent[v]!=w: return False vi, wi = self.node[v], self.node[w] self.Tree.set(vi, weight) def prod(self, l, r): sml, smr = self.e, self.e while True: li, ri = self.node[l], self.node[r] # print(l, r) if self.top[l]==self.top[r]: if self.depth[l]>self.depth[r]: sml = self.op(sml, self.Tree.prod(li, ri)) else: smr = self.op(self.Tree.prod(ri, li), smr) return self.op(sml, smr) else: l_top, r_top = self.top[l], self.top[r] if self.depth[l_top]>self.depth[r_top]: sml = self.op(sml, self.Tree.prod(li, self.node[l_top]+1)) l = self.parent[l_top] else: smr = self.op(self.Tree.prod(ri, self.node[r_top]+1), smr) r = self.parent[r_top] def __build_1(self, v0): for v1, _ in self.G[v0]: if v1==self.parent[v0]: continue else: self.parent[v1] = v0 self.depth[v1] = self.depth[v0]+1 self.size[v0] += self.__build_1(v1) temp = self.heavy[v0] if temp==-1 or self.size[temp]>= 1 r >>= 1 return self.op(sml, smr) def set(self, i, x): i += self.size self.data[i] = x while i>1: i >>= 1 self.data[i] = self.op(self.data[i<<1], self.data[(i<<1)|1]) def get(self, i): return self.data[i+self.size] def all_prod(self): return self.data[1] def max_right(self, l, f): if l==self.n: return self.n l += self.size sm = self.e while True: while l&1==0: l >>= 1 if not f(self.op(sm, self.data[l])): while l1: r >>= 1 if not f(self.op(self.data[r], sm)): while r