結果

問題 No.650 行列木クエリ
ユーザー toyuzukotoyuzuko
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Tree():
def __init__(self, n, edge):
self.n = n
self.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 = root
self.parent = [None for _ in range(self.n)]
self.parent[root] = -1
self.depth = [None for _ in range(self.n)]
self.depth[root] = 0
self.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] = node
self.depth[adj] = self.depth[node] + 1
self.order.append(adj)
stack.append(adj)
for node in self.order[::-1]:
for adj in self.tree[node]:
if self.parent[node] == adj:
continue
self.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.root
self.next = [None for _ in range(self.n)]
stack = [self.root]
order = 0
while stack:
node = stack.pop()
self.order[node] = order
order += 1
maxsize = 0
for adj in self.tree[node]:
if self.parent[node] == adj:
continue
if maxsize < self.size[adj]:
maxsize = self.size[adj]
self.next[node] = adj
for adj in self.tree[node]:
if self.parent[node] == adj or self.next[node] == adj:
continue
self.head[adj] = adj
stack.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, u
if 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 res
def 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, u
if self.head[u] != self.head[v]:
v = self.parent[self.head[v]]
else:
return u
class SegmentTree():
def __init__(self, arr, func=min, ie=2**63):
self.h = (len(arr) - 1).bit_length()
self.n = 2**self.h
self.ie = ie
self.func = func
self.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.n
self.tree[idx] = x
while idx:
idx >>= 1
self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])
def query(self, lt, rt):
lt += self.n
rt += self.n
vl = vr = self.ie
while rt - lt > 0:
if lt & 1:
vl = self.func(vl, self.tree[lt])
lt += 1
if rt & 1:
rt -= 1
vr = self.func(self.tree[rt], vr)
lt >>= 1
rt >>= 1
return self.func(vl, vr)
import sys
input = sys.stdin.readline
MOD = 1000000007
N = 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 = x
y00, y01, y10, y11 = y
z00 = (x00 * y00 + x01 * y10) % MOD
z01 = (x00 * y01 + x01 * y11) % MOD
z10 = (x10 * y00 + x11 * y10) % MOD
z11 = (x10 * y01 + x11 * y11) % MOD
return z00, z01, z10, z11
arr = [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 b
st.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)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0