結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,992 KB
testcase_01 AC 337 ms
91,308 KB
testcase_02 AC 471 ms
117,292 KB
testcase_03 AC 41 ms
52,992 KB
testcase_04 AC 321 ms
91,920 KB
testcase_05 AC 478 ms
116,940 KB
testcase_06 AC 40 ms
53,120 KB
testcase_07 AC 42 ms
53,120 KB
testcase_08 AC 248 ms
90,112 KB
testcase_09 AC 346 ms
116,852 KB
testcase_10 AC 41 ms
52,864 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0