結果
問題 | No.650 行列木クエリ |
ユーザー |
![]() |
提出日時 | 2020-05-12 22:30:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 605 ms / 2,000 ms |
コード長 | 4,913 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 139,400 KB |
最終ジャッジ日時 | 2024-09-14 00:55:20 |
合計ジャッジ時間 | 4,645 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
class Tree():def __init__(self, n, edge):self.n = nself.tree = [[] for _ in range(n)]for e in edge:self.tree[e[0]].append(e[1])self.tree[e[1]].append(e[0])def setroot(self, root):self.root = rootself.parent = [None for _ in range(self.n)]self.parent[root] = -1self.depth = [None for _ in range(self.n)]self.depth[root] = 0self.order = []self.order.append(root)self.size = [1 for _ in range(self.n)]stack = [root]while stack:node = stack.pop()for adj in self.tree[node]:if self.parent[adj] is None:self.parent[adj] = nodeself.depth[adj] = self.depth[node] + 1self.order.append(adj)stack.append(adj)for node in self.order[::-1]:for adj in self.tree[node]:if self.parent[node] == adj:continueself.size[node] += self.size[adj]def heavylight_decomposition(self):self.order = [None for _ in range(self.n)]self.head = [None for _ in range(self.n)]self.head[self.root] = self.rootself.next = [None for _ in range(self.n)]stack = [self.root]order = 0while stack:node = stack.pop()self.order[node] = orderorder += 1maxsize = 0for adj in self.tree[node]:if self.parent[node] == adj:continueif maxsize < self.size[adj]:maxsize = self.size[adj]self.next[node] = adjfor adj in self.tree[node]:if self.parent[node] == adj or self.next[node] == adj:continueself.head[adj] = adjstack.append(adj)if self.next[node] is not None:self.head[self.next[node]] = self.head[node]stack.append(self.next[node])def range_hld(self, u, v, edge=False):res = []while True:if self.order[u] > self.order[v]: u, v = v, uif self.head[u] != self.head[v]:res.append((self.order[self.head[v]], self.order[v] + 1))v = self.parent[self.head[v]]else:res.append((self.order[u] + edge, self.order[v] + 1))return resdef subtree_hld(self, u):return self.order[u], self.order[u] + self.size[u]def lca_hld(self, u, v):while True:if self.order[u] > self.order[v]: u, v = v, uif self.head[u] != self.head[v]:v = self.parent[self.head[v]]else:return uclass SegmentTree():def __init__(self, arr, func=min, ie=2**63):self.h = (len(arr) - 1).bit_length()self.n = 2**self.hself.ie = ieself.func = funcself.tree = [ie for _ in range(2 * self.n)]for i in range(len(arr)):self.tree[self.n + i] = arr[i]for i in range(1, self.n)[::-1]:self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])def set(self, idx, x):idx += self.nself.tree[idx] = xwhile idx:idx >>= 1self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])def query(self, lt, rt):lt += self.nrt += self.nvl = vr = self.iewhile rt - lt > 0:if lt & 1:vl = self.func(vl, self.tree[lt])lt += 1if rt & 1:rt -= 1vr = self.func(self.tree[rt], vr)lt >>= 1rt >>= 1return self.func(vl, vr)import sysinput = sys.stdin.readlineMOD = 1000000007N = int(input())E = [tuple(map(int, input().split())) for _ in range(N - 1)]t = Tree(N, E)t.setroot(0)t.heavylight_decomposition()ie = (1, 0, 0, 1)def mmul(x, y):x00, x01, x10, x11 = xy00, y01, y10, y11 = yz00 = (x00 * y00 + x01 * y10) % MODz01 = (x00 * y01 + x01 * y11) % MODz10 = (x10 * y00 + x11 * y10) % MODz11 = (x10 * y01 + x11 * y11) % MODreturn z00, z01, z10, z11arr = [ie for _ in range(N)]st = SegmentTree(arr, mmul, ie)Q = int(input())res = []for _ in range(Q):q = input()if q[0] == 'x':i, x00, x01, x10, x11 = map(int, q[1:].split())a, b = E[i]ch = a if t.parent[a] == b else bst.set(t.order[ch], (x00, x01, x10, x11))else:c = (1, 0, 0, 1)i, j = map(int, q[1:].split())for lt, rt in t.range_hld(i, j, edge=True):c = mmul(st.query(lt, rt), c)res.append(' '.join(map(str, c)))print('\n'.join(map(str, res)))