#yukicoder 529 帰省ラッシュ #Lowlink(二重辺連結成分分解) class Lowlink: def __init__(self, N, G): #連結とは限らないグラフGを隣接リストとして受け取る #articulation[i]: 頂点iが関節点ならTrue 特に、連結成分が1つだけのグラフはFalse #root[i]: 頂点iが属するDFS木の代表値 #leader[i]: 頂点iが属する二重辺連結成分の代表値 (特に、橋で切ったグラフの代表値) #size[i]: 頂点iが属する二重辺連結成分の大きさ (同上) #child[i], bridge[i]: 探索時の有向隣接リスト 特に、それが橋ならbridge[i]へ self._N = N; self._G = G; self.pre = pre = [N] * N + [0]; self.low = low = [N] * N self.articulation = A = [False] * N; self.root = root = [-1] * N self.leader = leader = [-1] * N; self.size = size = [0] * N self.child = C = [[] for _ in range(N)]; self.bridge = B = [[] for _ in range(N)] for parent in range(N): if pre[parent] != N: size[parent] = size[ leader[parent] ]; continue Q = [(parent, -1)] while Q: now, back = Q.pop() if now >= 0: if pre[now] == N: pre[now] = low[now] = pre[-1]; pre[-1] += 1 root[now] = parent; Q.append((~now, back)) else: low[back] = min(low[back], pre[now]); continue for nxt in G[now]: if nxt != back: Q.append((nxt, now)) else: now = ~now if now == parent: continue B[back].append(now) if pre[back] < low[now] else C[back].append(now) low[back] = min(low[back], low[now]) Q = [(parent, -1, parent)] while Q: now, back, top = Q.pop(); leader[now] = top; size[top] += 1 for nxt in C[now]: if pre[now] <= low[nxt]: A[now] = True Q.append((nxt, now, top)) for nxt in B[now]: if pre[now] <= low[nxt]: A[now] = True Q.append((nxt, now, nxt)) if now == parent: A[now] = ( len(C[now]) + len(B[now]) >= 2 ) pre.pop(); return #Heavy-Light decomposition データ構造を使うならbuild必須なので注意 class HL_decomposition: class SegmentTree: #前提mod1 def __init__(self, n, identity_e, function): self._n = n; self._size = 1 << (n - 1).bit_length(); self._e = e = identity_e; self._f = function; self._node = [e] * 2 * self._size def build(self, A): for i,v in enumerate(A, start = self._size): self._node[i] = v for i in range(self._size - 1, 0, -1): self._node[i] = self._f(self._node[i<<1], self._node[i<<1|1]) def update(self, index, value): i = self._size + index; self._node[i] = value while i - 1: i >>= 1; self._node[i] = self._f(self._node[i<<1], self._node[i<<1|1]) def fold(self, Lt, Rt): Lt, Rt = Lt + self._size, Rt + self._size; vL = vR = self._e while Lt < Rt: if Lt & 1: vL = self._f(vL, self._node[Lt]); Lt += 1 if Rt & 1: Rt -= 1; vR = self._f(self._node[Rt], vR) Lt >>= 1; Rt >>= 1 return self._f(vL, vR) class SparseTable: #前提mod2 def __init__(self, n, identity_e, function): self._n = n; self._logn = (n - 1).bit_length(); self._size = 1 << self._logn; self._e = e = identity_e; self._f = function; self._T = [[e] * self._logn for _ in range(self._size)]; self._A = [e] * self._size def build(self, A): e, f, T = self._e, self._f, self._T; self._A = A = A + [e] * (self._size - self._n) for x in range(self._logn): t = 1 << x for s in range(t, self._size, t << 1): T[s][x] = A[s] for j in range(s + 1, s + t, +1): T[j][x] = f(T[j-1][x], A[j]) for s in range(self._size - t - 1, -1, - t << 1): T[s][x] = A[s] for j in range(s - 1, s - t, -1): T[j][x] = f(A[j], T[j+1][x]) def fold(self, Lt, Rt): Lt, Rt = max(0, Lt), min(self._size, Rt) - 1; x = (Lt ^ Rt).bit_length() - 1; return self._e if not 0 <= Lt <= Rt < self._size else self._A[Lt] if Lt == Rt else self._f( self._T[Lt][x], self._T[Rt][x] ) def __init__(self, N, G, identity_e = 0, func = 'add'): #pos[v] = i, order[i] = v 頂点vのDFS順序がi番目 #leader[i]: Heavy edgeの代表値のDFS順序 #depth[i]: 再帰の深さ parent[i]: ひとつ根側のDFS順序 #A[i]: u - vパスの重みw。DFS順序が遅い頂点v側に入れる。pos[u] < pos[v] = i self._N = N; self._logN = logN = N.bit_length(); self._e = e = identity_e self._f = f = (lambda x,y: x + y) if func == 'add' else func self._G = G = [[(v, e) for v in S] for S in G] if N > 1 and isinstance(G[0][0],int) else G self._A = A = [e for _ in range(N)]; self.pos = pos = [-1] * N self.order = order = [-1] * N; self.leader = leader = [-1] * N; size = [1] * N self.depth = depth = [-1] * N; self.parent = parent = [-1] * N; Q = [(0, -1)] for now,back in Q: #前処理 for nxt,_ in G[now]: if nxt != back: Q.append((nxt, now)) while Q: now,back = Q.pop(); size[back] += size[now] if back != -1 else 0 Q.append((0, -1, e, 0, -1)) #HL分解 for i in range(N): now, back, c, d, t = Q.pop(); pos[now], parent[i]= i, pos[back] order[i], A[i], depth[i] = now, c, d; leader[i] = t = t if t != -1 else i if size[now] > 1: #部分木のうち最大サイズのものを最後にappend s, v, x = 0, now, e for nxt,w in G[now]: if nxt == back: continue if s < size[nxt]: if s > 0: Q.append((v, now, x, d + 1, -1)) s, v, x = size[nxt], nxt, w else: Q.append((nxt, now, w, d + 1, -1)) Q.append((v, now, x, d, t)) def build(self, use_SegTree = True, A = 'no need to import'): N, e, f = self._N, self._e, self._f if A != 'no need to import': self._A = A self._ST = ST = self.SegmentTree if use_SegTree else self.SparseTable self._obvST = obvST = ST(N, e, f); obvST.build(self._A) self._revST = revST = ST(N, e, f); revST.build(self._A[::-1]) def LCA(self, u, v): #O(logN) i, j = self.pos[u], self.pos[v]; c, d = self.depth[i], self.depth[j] if c > d: i, j, c, d = j, i, c, d s, t = self.leader[i], self.leader[j] for d in range(d - 1, c - 1, -1): j = self.parent[t]; t = self.leader[j] while s != t: i, j = self.parent[s], self.parent[t]; s, t = self.leader[i], self.leader[j] return self.order[ min(i,j) ] def update(self, index_u, value_v, weight = None): if weight == None: j, w = self.pos[index_u], value_v else: i, j, w = self.pos[index_u], self.pos[value_v], weight; i, j = (j, i) if i > j else (i, j); assert self.parent[j] == i, 'not connect Tree edge' self._A[j] = w; self._obvST.update(j, w); self._revST.update(self._N - 1 - j, w) def fold(self, u, v, path_query = False): #u→vパスの作用値を取得 Lt = Rt = self._e; f = self._f; i, j = self.pos[u], self.pos[v] c, d = self.depth[i], self.depth[j]; s, t = self.leader[i], self.leader[j] for c in range(c - 1, d - 1, -1): Lt = f( Lt, self._revST.fold(N - 1 - i, N - s) ); i = self.parent[s]; s = self.leader[i] for d in range(d - 1, c - 1, -1): Rt = f( self._obvST.fold(t, j + 1), Rt ); j = self.parent[t]; t = self.leader[j] while s != t: Lt, Rt = f( Lt, self._revST.fold(N-1-i,N-s) ), f( self._obvST.fold(t,j+1), Rt ); i, j = self.parent[s], self.parent[t]; s, t = self.leader[i], self.leader[j] if i > j: LCA, Lt = j, f( Lt, self._revST.fold(N - i - 1, N - j - 1) ) elif i < j: LCA, Rt = i, f( self._obvST.fold(i + 1, j + 1), Rt ) else: LCA = i LCA = self._e if path_query else self._A[LCA]; return f( f(Lt, LCA), Rt ) import heapq #入力受取 N,M,Q = map(int,input().split()) G = [[] for _ in range(N)] for _ in range(M): a,b = map(lambda x: int(x) - 1, input().split()) G[a].append(b) G[b].append(a) query = [] for _ in range(Q): t,u,v = map(int,input().split()) if t == 1: query.append((t, u-1, v)) if t == 2: query.append((t, u-1, v-1)) #与えられたグラフを二重辺連結成分分解 leaderの値を座標圧縮 L = Lowlink(N, G) C = sorted(set(L.leader)); C = {j:i for i,j in enumerate(C)} #座標圧縮後の木を作る nG = [set() for _ in range(len(C))] for u in range(N): for v in G[u]: if u < v: nu,nv = C[L.leader[u]], C[L.leader[v]] if nu != nv: nG[nu].add(nv); nG[nv].add(nu) G = [list(S) for S in nG] N = len(C) for i in range(Q): t,u,v = query[i] if t == 1: query[i] = (t, C[L.leader[u]], v) if t == 2: query[i] = (t, C[L.leader[u]], C[L.leader[v]]) #座標圧縮後の木をHL分解 SegTreeには(最大の価値, 現在値)を格納 HLD = HL_decomposition(N, G, (0, 0), max) HLD.build(True, [(0, i) for i in range(N)]) #各連結成分ごとに最大の獲物の価値を格納するheapqを用意 負値で入れるので注意 prey = [[] for _ in range(N)] #クエリに回答 for t,u,v in query: if t == 1: #SegTreeの更新有無を判定 now_max = 0 if len(prey[u]) >= 1: now_max = - prey[u][0] heapq.heappush(prey[u], - v) if now_max < v: HLD.update(u, (v, u)) if t == 2: #最大の獲物を取得 max_prey, point = HLD.fold(u, v, False) if max_prey == 0: print(-1) continue else: print(max_prey) #獲物を削除する heapq.heappop(prey[point]) now_max = 0 if len(prey[point]) >= 1: now_max = - prey[point][0] #更新 HLD.update(point, (now_max, point))