結果

問題 No.650 行列木クエリ
ユーザー lam6er
提出日時 2025-03-26 15:59:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,600 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 136,240 KB
最終ジャッジ日時 2025-03-26 15:59:58
合計ジャッジ時間 5,768 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 10**9 + 7

def main():
    input = sys.stdin.read().split()
    ptr = 0

    n = int(input[ptr])
    ptr += 1

    # Read edges and build adjacency list
    adj = [[] for _ in range(n)]
    raw_edges = []
    for i in range(n-1):
        a = int(input[ptr])
        b = int(input[ptr+1])
        ptr +=2
        raw_edges.append((a, b))
        adj[a].append((b, i))
        adj[b].append((a, i))

    # BFS to determine parent and edge_index for each node
    parent = [-1] * n
    edge_index = [-1] * n  # edge from parent to current node
    q = deque([0])
    parent[0] = -1
    while q:
        u = q.popleft()
        for v, i in adj[u]:
            if parent[v] == -1 and v != 0:
                parent[v] = u
                edge_index[v] = i
                q.append(v)

    # Initialize matrices for edges, all identity matrices
    matrix = [ [[1,0], [0,1]] for _ in range(n-1) ]

    q = int(input[ptr])
    ptr +=1

    for _ in range(q):
        query_type = input[ptr]
        ptr +=1
        if query_type == 'x':
            # Update query
            i = int(input[ptr])
            ptr +=1
            x00 = int(input[ptr]) % MOD
            x01 = int(input[ptr+1]) % MOD
            x10 = int(input[ptr+2]) % MOD
            x11 = int(input[ptr+3]) % MOD
            ptr +=4
            matrix[i] = [ [x00, x01], [x10, x11] ]
        else:
            # Get query, i is ancestor of j
            i = int(input[ptr])
            j = int(input[ptr+1])
            ptr +=2

            # Collect the path from j to i
            path = []
            current = j
            while current != i:
                e = edge_index[current]
                if e == -1:
                    break  # should not happen as i is ancestor
                path.append(e)
                current = parent[current]

            # Reverse the path to get i to j order
            path.reverse()

            # Compute matrix product
            res = [[1, 0], [0, 1]]
            for e in path:
                m = matrix[e]
                a00 = res[0][0] * m[0][0] + res[0][1] * m[1][0]
                a01 = res[0][0] * m[0][1] + res[0][1] * m[1][1]
                a10 = res[1][0] * m[0][0] + res[1][1] * m[1][0]
                a11 = res[1][0] * m[0][1] + res[1][1] * m[1][1]
                res = [
                    [a00 % MOD, a01 % MOD],
                    [a10 % MOD, a11 % MOD]
                ]

            # Output the result
            print(f"{res[0][0]} {res[0][1]} {res[1][0]} {res[1][1]}")

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