結果

問題 No.650 行列木クエリ
ユーザー qwewe
提出日時 2025-05-14 12:51:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,947 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 152,080 KB
最終ジャッジ日時 2025-05-14 12:53:06
合計ジャッジ時間 7,089 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 10**9 + 7

class Matrix:
    def __init__(self):
        self.a = [[1, 0], [0, 1]]  # Identity matrix
    def update(self, x00, x01, x10, x11):
        self.a = [[x00 % MOD, x01 % MOD], [x10 % MOD, x11 % MOD]]
    def multiply(self, other):
        res = Matrix()
        res.a[0][0] = (self.a[0][0] * other.a[0][0] + self.a[0][1] * other.a[1][0]) % MOD
        res.a[0][1] = (self.a[0][0] * other.a[0][1] + self.a[0][1] * other.a[1][1]) % MOD
        res.a[1][0] = (self.a[1][0] * other.a[0][0] + self.a[1][1] * other.a[1][0]) % MOD
        res.a[1][1] = (self.a[1][0] * other.a[0][1] + self.a[1][1] * other.a[1][1]) % MOD
        return res

def main():
    sys.setrecursionlimit(1 << 25)
    n = int(sys.stdin.readline())
    edges = [[] for _ in range(n)]
    raw_edges = []
    for i in range(n-1):
        a, b = map(int, sys.stdin.readline().split())
        raw_edges.append((a, b))
        edges[a].append((b, i))
        edges[b].append((a, i))
    
    parent = [-1] * n
    parent_edge = [-1] * n  # parent_edge[v] is the edge index from v to its parent
    children = [[] for _ in range(n)]
    edge_info = [None] * (n-1)  # edge_info[i] = (parent, child)
    visited = [False] * n
    q = deque([0])
    visited[0] = True
    while q:
        u = q.popleft()
        for v, i in edges[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                parent_edge[v] = i
                children[u].append(v)
                edge_info[i] = (u, v)
                q.append(v)
    
    # HLD preparation
    size = [0] * n
    depth = [0] * n
    heavy = [-1] * n
    chain = [i for i in range(n)]
    
    def dfs_size(u):
        size[u] = 1
        max_size = 0
        for v in children[u]:
            depth[v] = depth[u] + 1
            dfs_size(v)
            size[u] += size[v]
            if size[v] > max_size:
                max_size = size[v]
                heavy[u] = v
    
    dfs_size(0)
    
    def dfs_hld(u, current_chain):
        chain[u] = current_chain
        if heavy[u] != -1:
            dfs_hld(heavy[u], current_chain)
            for v in children[u]:
                if v != heavy[u]:
                    dfs_hld(v, v)
    
    dfs_hld(0, 0)
    
    matrices = [Matrix() for _ in range(n-1)]
    
    def get_path_edges(u, ancestor):
        path = []
        while u != ancestor:
            if chain[u] == chain[ancestor]:
                # Same chain, collect up to ancestor
                while u != ancestor:
                    e = parent_edge[u]
                    if e == -1:
                        break  # root node
                    path.append(e)
                    u = parent[u]
                break
            else:
                # Move to chain head
                head = chain[u]
                while u != head:
                    e = parent_edge[u]
                    path.append(e)
                    u = parent[u]
                # Move to parent of head
                if head == 0:
                    break  # cannot go above root
                e = parent_edge[head]
                path.append(e)
                u = parent[head]
        return path
    
    q = int(sys.stdin.readline())
    for _ in range(q):
        parts = sys.stdin.readline().split()
        if parts[0] == 'x':
            i = int(parts[1])
            x00 = int(parts[2])
            x01 = int(parts[3])
            x10 = int(parts[4])
            x11 = int(parts[5])
            matrices[i].update(x00, x01, x10, x11)
        else:
            i = int(parts[1])
            j = int(parts[2])
            edges_list = get_path_edges(j, i)
            edges_list.reverse()
            res = Matrix()
            for e in edges_list:
                res = res.multiply(matrices[e])
            print(res.a[0][0], res.a[0][1], res.a[1][0], res.a[1][1])

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