結果

問題 No.650 行列木クエリ
ユーザー toyuzukotoyuzuko
提出日時 2020-05-12 22:30:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 605 ms / 2,000 ms
コード長 4,913 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 139,400 KB
最終ジャッジ日時 2024-09-14 00:55:20
合計ジャッジ時間 4,645 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
55,164 KB
testcase_01 AC 319 ms
96,028 KB
testcase_02 AC 605 ms
139,400 KB
testcase_03 AC 40 ms
54,648 KB
testcase_04 AC 314 ms
96,060 KB
testcase_05 AC 597 ms
139,020 KB
testcase_06 AC 41 ms
54,624 KB
testcase_07 AC 41 ms
54,004 KB
testcase_08 AC 275 ms
96,004 KB
testcase_09 AC 447 ms
138,652 KB
testcase_10 AC 40 ms
55,040 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0]].append(e[1])
            self.tree[e[1]].append(e[0])

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

MOD = 1000000007

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

t = Tree(N, E)
t.setroot(0)
t.heavylight_decomposition()

ie = (1, 0, 0, 1)

def mmul(x, y):
    x00, x01, x10, x11 = x
    y00, y01, y10, y11 = y
    z00 = (x00 * y00 + x01 * y10) % MOD
    z01 = (x00 * y01 + x01 * y11) % MOD
    z10 = (x10 * y00 + x11 * y10) % MOD
    z11 = (x10 * y01 + x11 * y11) % MOD
    return z00, z01, z10, z11

arr = [ie for _ in range(N)]

st = SegmentTree(arr, mmul, ie)

Q = int(input())

res = []

for _ in range(Q):
    q = input()
    if q[0] == 'x':
        i, x00, x01, x10, x11 = map(int, q[1:].split())
        a, b = E[i]
        ch = a if t.parent[a] == b else b
        st.set(t.order[ch], (x00, x01, x10, x11))
    else:
        c = (1, 0, 0, 1)
        i, j = map(int, q[1:].split())
        for lt, rt in t.range_hld(i, j, edge=True):
            c = mmul(st.query(lt, rt), c)
        res.append(' '.join(map(str, c)))

print('\n'.join(map(str, res)))
0