結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2020-04-23 01:44:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 3,336 bytes |
コンパイル時間 | 284 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 117,292 KB |
最終ジャッジ日時 | 2024-10-12 12:31:29 |
合計ジャッジ時間 | 3,537 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesMOD = 10 ** 9 + 7N = int(readline())graph = [[] for _ in range(N + 1)]edges = [tuple(map(lambda x: int(x) + 1, readline().split())) for _ in range(N - 1)]for a, b in edges:graph[a].append(b)graph[b].append(a)parent = [0] * (N + 1)def HLD(graph, root=1):global parentN = len(graph)order = []stack = [root]while stack:x = stack.pop()order.append(x)if parent[x]:graph[x].remove(parent[x])for y in graph[x]:parent[y] = xstack.append(y)size = [1] * Nfor p in order[::-1]:A = graph[p]for i in range(len(A)):x = size[A[i]]if x > size[A[0]]:A[0], A[i] = A[i], A[0]size[p] += xind = [0] * Nhead = [0] * Nhead[root] = rootstack = [root]order = []while stack:x = stack.pop()ind[x] = len(order)order.append(x)for y in graph[x][1:]:head[y] = ystack.append(y)for y in graph[x][:1]:head[y] = head[x]stack.append(y)return order, ind, headdef mult(A, B):a, b, c, d = Ap, q, r, s = Ba, b, c, d = a * p + b * r, a * q + b * s, c * p + d * r, c * q + d * sreturn (a % MOD, b % MOD, c % MOD, d % MOD)class SegTree:""" segment tree with point modification and range product access. """data_unit = (1, 0, 0, 1)@classmethoddef data_f(cls, A, B):return mult(A, B)def __init__(self, N):self.N = Nself.data = [self.data_unit] * (N + N)def build(self, raw_data):data = self.dataf = self.data_fN = self.Ndata[N:] = raw_data[:]for i in range(N - 1, 0, -1):data[i] = f(data[i << 1], data[i << 1 | 1])def set_val(self, i, x):data = self.dataf = self.data_fi += self.Ndata[i] = xwhile i > 1:i >>= 1data[i] = f(data[i << 1], data[i << 1 | 1])def fold(self, L, R):""" compute for [L, R) """vL = vR = self.data_unitdata = self.dataf = self.data_fL += self.NR += self.Nwhile L < R:if L & 1:vL = f(vL, data[L])L += 1if R & 1:R -= 1vR = f(data[R], vR)L >>= 1R >>= 1return f(vL, vR)_, ind, head = HLD(graph)seg = SegTree(N)edge_ind = [0] * (N - 1)for i, (a, b) in enumerate(edges):if parent[a] == b:edge_ind[i] = ind[a]else:edge_ind[i] = ind[b]Q = int(readline())for query in readlines():if query.startswith(b'x'):i, a, b, c, d = map(int, query[1:].split())seg.set_val(edge_ind[i], (a, b, c, d))continueu, v = map(int, query[1:].split())u += 1v += 1A = (1, 0, 0, 1)h = head[u]while h != head[v]:p = head[v]B = seg.fold(ind[p], ind[v] + 1)A = mult(B, A)v = parent[head[v]]if u != v:B = seg.fold(ind[u] + 1, ind[v] + 1)A = mult(B, A)print(*A)