結果

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

ソースコード

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
N = 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 parent
N = 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] = x
stack.append(y)
size = [1] * N
for 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] += x
ind = [0] * N
head = [0] * N
head[root] = root
stack = [root]
order = []
while stack:
x = stack.pop()
ind[x] = len(order)
order.append(x)
for y in graph[x][1:]:
head[y] = y
stack.append(y)
for y in graph[x][:1]:
head[y] = head[x]
stack.append(y)
return order, ind, head
def mult(A, B):
a, b, c, d = A
p, q, r, s = B
a, b, c, d = a * p + b * r, a * q + b * s, c * p + d * r, c * q + d * s
return (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)
@classmethod
def data_f(cls, A, B):
return mult(A, B)
def __init__(self, N):
self.N = N
self.data = [self.data_unit] * (N + N)
def build(self, raw_data):
data = self.data
f = self.data_f
N = self.N
data[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.data
f = self.data_f
i += self.N
data[i] = x
while i > 1:
i >>= 1
data[i] = f(data[i << 1], data[i << 1 | 1])
def fold(self, L, R):
""" compute for [L, R) """
vL = vR = self.data_unit
data = self.data
f = self.data_f
L += self.N
R += self.N
while L < R:
if L & 1:
vL = f(vL, data[L])
L += 1
if R & 1:
R -= 1
vR = f(data[R], vR)
L >>= 1
R >>= 1
return 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))
continue
u, v = map(int, query[1:].split())
u += 1
v += 1
A = (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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0