結果

問題 No.650 行列木クエリ
ユーザー tamatotamato
提出日時 2020-05-04 16:54:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 855 ms / 2,000 ms
コード長 4,455 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 87,580 KB
実行使用メモリ 150,956 KB
最終ジャッジ日時 2023-09-06 22:30:54
合計ジャッジ時間 6,333 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 99 ms
72,568 KB
testcase_01 AC 550 ms
102,544 KB
testcase_02 AC 806 ms
150,956 KB
testcase_03 AC 100 ms
72,824 KB
testcase_04 AC 563 ms
103,928 KB
testcase_05 AC 855 ms
150,852 KB
testcase_06 AC 97 ms
72,532 KB
testcase_07 AC 99 ms
72,564 KB
testcase_08 AC 629 ms
109,488 KB
testcase_09 AC 768 ms
142,684 KB
testcase_10 AC 93 ms
72,104 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    def matmul(A, B):
        C = [[0] * len(B[0]) for _ in range(len(A))]
        for i in range(len(A)):
            for k in range(len(B)):
                for j in range(len(B[0])):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
        return C

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

    N = int(input())
    adj = [[] for _ in range(N + 1)]
    E = [[] for _ in range(N-1)]
    for e in range(N - 1):
        a, b = map(int, input().split())
        a += 1
        b += 1
        adj[a].append(b)
        adj[b].append(a)
        E[e] = (a, b)

    que = deque()
    que.append(1)
    depth = [-1] * (N + 1)
    depth[1] = 0
    par = [0] * (N + 1)
    child = [[] for _ in range(N + 1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if depth[u] == -1:
                depth[u] = depth[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    size = [1] * (N + 1)
    largest_child = [0] * (N + 1)
    for v in seq:
        child_size_max = 0
        for u in child[v]:
            size[v] += size[u]
            if size[u] > child_size_max:
                child_size_max = size[u]
                largest_child[v] = u

    seq.reverse()
    idx_of_array = [0] * (N + 1)
    idx_in_array = [0] * (N + 1)
    seen = [0] * (N + 1)
    compressed_tree = []
    for v in seq:
        if seen[v]:
            continue
        seen[v] = 1
        compressed_tree.append([v])
        idx_of_array[v] = len(compressed_tree) - 1
        idx_in_array[v] = 0
        p = v
        cnt = 0
        while largest_child[p]:
            cnt += 1
            u = largest_child[p]
            seen[u] = 1
            compressed_tree[-1].append(u)
            idx_of_array[u] = len(compressed_tree) - 1
            idx_in_array[u] = cnt
            p = u

    ST = []
    for i in range(len(compressed_tree)):
        ST.append(SegmentTree(compressed_tree[i], initialize=False, segfunc=matmul, ident=[[1, 0], [0, 1]]))

    for _ in range(int(input())):
        q = list(input().split())
        if q[0] == "x":
            q = q[1:]
            e, a, b, c, d = map(int, q)
            v1, v2 = E[e]
            if depth[v1] < depth[v2]:
                v = v2
            else:
                v = v1
            ST[idx_of_array[v]].update(idx_in_array[v] + 1, [[a, b], [c, d]])
        else:
            q = q[1:]
            a, d = map(int, q)
            a += 1
            d += 1
            ans = [[1, 0], [0, 1]]
            while idx_of_array[a] != idx_of_array[d]:
                ans = matmul(ST[idx_of_array[d]].query(1, idx_in_array[d] + 2), ans)
                d = par[compressed_tree[idx_of_array[d]][0]]
            if a != d:
                ans = matmul(ST[idx_of_array[a]].query(idx_in_array[a] + 2, idx_in_array[d] + 2), ans)
            print(ans[0][0], ans[0][1], ans[1][0], ans[1][1])


if __name__ == '__main__':
    main()
0