結果

問題 No.650 行列木クエリ
ユーザー navel_tosnavel_tos
提出日時 2024-09-06 13:17:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,634 ms / 2,000 ms
コード長 8,801 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 162,216 KB
最終ジャッジ日時 2024-09-06 13:17:23
合計ジャッジ時間 10,710 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
55,080 KB
testcase_01 AC 1,312 ms
127,292 KB
testcase_02 AC 1,428 ms
160,136 KB
testcase_03 AC 43 ms
54,900 KB
testcase_04 AC 1,222 ms
127,140 KB
testcase_05 AC 1,534 ms
161,856 KB
testcase_06 AC 42 ms
55,460 KB
testcase_07 AC 42 ms
55,304 KB
testcase_08 AC 1,156 ms
126,140 KB
testcase_09 AC 1,634 ms
162,216 KB
testcase_10 AC 41 ms
55,292 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#HL分解(分解のみ)
#Heavy-Light decomposition
class HL_decomposition:
    def __init__(self, N, G, root = 0):
        #頂点iのDFS到達順をTiと記述する
        #order[Ti] = i, visit[i] = depth[i] << 31 | Ti
        #steps[Ti] = Hv.edge左端Ti << 31 | Hv.edge左端から1つ戻った頂点のTi
        self._N = N
        self._order = order = [0] * N
        self._visit = visit = [1] * N  #sizeの代用
        self._steps = steps = [root << 31 | N] * N
        self._mask31 = mask31 = (1 << 31) - 1
        stack = [root]
        for now in stack:
            visit[now] = 0
            for nxt in G[now]:
                if visit[nxt] == 1: stack.append(nxt)
        while stack:
            now = stack.pop()
            visit[now] = 1
            for nxt in G[now]:
                if visit[nxt] != 0: visit[now] += visit[nxt]
        stack.append(root << 31 | N)
        for Ti in range(N):
            x = stack.pop()
            now, Lt = x >> 31, x & mask31
            order[Ti] = now
            if Lt >= N: steps[Ti], Lt = Ti << 31 | Lt - N, Ti
            else: steps[Ti] = steps[Lt]
            d = visit[now] >> 31
            if now != root and len(G[now]) <= 1: continue
            maxsize = leader = 0
            for nxt in G[now]:
                if visit[nxt] & mask31 > visit[now] & mask31: continue
                if maxsize < visit[nxt] & mask31:
                    if maxsize != 0:
                        visit[leader] |= (d + 1) << 31
                        stack.append(leader << 31 | N + Ti)
                    maxsize, leader = visit[nxt] & mask31, nxt
                else:
                    visit[nxt] |= (d + 1) << 31
                    stack.append(nxt << 31 | N + Ti)
            assert maxsize > 0
            visit[leader] |= d << 31
            stack.append(leader << 31 | Lt)
        for Ti, now in enumerate(order): visit[now] = visit[now] >> 31 << 31 | Ti

    def LCA(self, u, v):
        x, y = self._visit[u], self._visit[v]
        du, Tu, dv, Tv = x >> 31, x & self._mask31, y >> 31, y & self._mask31
        for du in range(du - 1, dv - 1, -1): Tu = self._steps[Tu] & self._mask31
        for dv in range(dv - 1, du - 1, -1): Tv = self._steps[Tv] & self._mask31
        while self._steps[Tu] >> 31 != self._steps[Tv] >> 31:
            Tu, Tv = self._steps[Tu] & self._mask31, self._steps[Tv] & self._mask31
        return self._order[ min(Tu, Tv) ]
    def find(self, u, v = None):  #max(Tu, Tv)
        if v == None: return self._visit[u] & self._mask31
        else: return max(self._visit[u] & self._mask31, self._visit[v] & self._mask31)
    def fold(self, u, v):
        '''
        (to, go, LCA_DFSorder)の順でu→vパスの作用区間を返す
        to[0], to[1], ・・・ , 必要なら array[LCA_DFSorder],  go[0], go[1], ・・・ の順で合成
        to: LCA ← uの方向  x ← f( x, prod[Lt ← Rt) )  合成方向は逆向きなので注意
        go: LCA → vの方向  y ← f( prod[Lt → Rt), y )
        '''
        x, y = self._visit[u], self._visit[v]
        du, Tu, dv, Tv = x >> 31, x & self._mask31, y >> 31, y & self._mask31
        x, y = self._steps[Tu], self._steps[Tv]
        Lu, Tw, Lv, Tx = x >> 31, x & self._mask31, y >> 31, y & self._mask31
        to, go = [], []
        for du in range(du - 1, dv - 1, -1):
            to.append((Lu, Tu + 1))
            Tu, x = Tw, self._steps[Tw]; Lu, Tw = x >> 31, x & self._mask31
        for dv in range(dv - 1, du - 1, -1):
            go.append((Lv, Tv + 1))
            Tv, y = Tx, self._steps[Tx]; Lv, Tx = y >> 31, y & self._mask31
        while Lu != Lv:
            to.append((Lu, Tu + 1)); go.append((Lv, Tv + 1))
            Tu, x = Tw, self._steps[Tw]; Lu, Tw = x >> 31, x & self._mask31         
            Tv, y = Tx, self._steps[Tx]; Lv, Tx = y >> 31, y & self._mask31
        if   Tu < Tv: go.append((Tu + 1, Tv + 1))
        elif Tu > Tv: to.append((Tv + 1, Tu + 1))
        go.reverse(); return to, go, min(Tu, Tv)
        

'''
#動作チェック: ABC014D
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(lambda x: int(x) - 1, input().split())
    G[u].append(v)
    G[v].append(u)
HLD = HL_decomposition(N, G)
for _ in range( int(input()) ):
    u, v = map(lambda x: int(x) - 1, input().split())
    ans = 0
    to, go, _ = HLD.fold(u, v)
    for Lt, Rt in to + go: ans += Rt - Lt
    print(ans + 1)
'''
#Segment Tree: O(logN)
class SegmentTree:
    def __init__(self, n, identity_e, combine_f): self._n = n; self._size = 1 << (n-1).bit_length(); self._identity_e = identity_e; self._combine_f = combine_f; self._node = [self._identity_e] * 2 * self._size
    def build(self, array):
        assert len(array) == self._n, 'array too large'
        for i, v in enumerate(array, start = self._size): self._node[i] = v
        for i in range(self._size - 1, 0, -1): self._node[i] = self._combine_f(self._node[i<<1|0], self._node[i<<1|1])
    def update(self, index, value):  #一点更新
        i = self._size + index; self._node[i] = value
        while i - 1: i >>= 1; self._node[i] = self._combine_f(self._node[i<<1|0], self._node[i<<1|1])
    def fold(self, L, R):  #区間取得: [L,R)の区間値を得る
        L += self._size; R += self._size; vL = vR = self._identity_e
        while L < R:
            if L & 1: vL = self._combine_f(vL, self._node[L]); L += 1
            if R & 1: R -= 1; vR = self._combine_f(self._node[R], vR)
            L >>= 1; R >>= 1
        return self._combine_f(vL, vR)
    
    #down: Falseなら単調増加、Trueなら単調減少を仮定する。
    #[Lt: Rt]の作用値がX以上/以下 となる、最小のRtを返す。閉区間なので扱い注意。
    def bisect(self, Lt, X, down = False):
        if Lt >= self._n: return self._n
        now = Lt + self._size; cnt = self._identity_e
        while 1:  #nodeの上昇
            f = now & 3; now = now >> 2 if f == 0 else now >> 1 if f == 2 else now; t = self._combine_f(cnt, self._node[now])
            if t != X and (down ^ (t < X)):
                cnt = t; now += 1
                if now & (now - 1) == 0: return self._n
            else: break  #(not down and t >= X, down and t <= X: break)
        while now < self._size:  #下降
            t = self._combine_f( cnt, self._node[now << 1 | 0] )
            if t != X and (down ^ (t < X)): cnt = t; now = now << 1 | 1
            else: now = now << 1
        return now - self._size


#行列累乗  1行N列の行列は[[1, 2, ...]] と2重括弧に自動変換するので注意
class matrix_pow:
    def __init__(self,MOD=998244353): self._MOD=MOD
    def eye(self,N):  #単位行列の作成
        return [[1 if i==j else 0 for j in range(N)] for i in range(N)]
    def add(self,A,B):  #行列の加算
        if isinstance(A[0],int): A=[A]
        if isinstance(B[0],int): B=[B]
        assert len(A)   ==len(B),    'not same size'
        assert len(A[0])==len(B[0]), 'not same size'
        nG=[[0]*max(len(A[i]) for i in range(len(A))) for _ in range(len(A))]
        for h in range(len(nG)):
            for w in range(len(nG[h])):
                if len(A[h])<w: nG[h][w]+=A[h][w]
                if len(B[h])<w: nG[h][w]+=B[h][w]
                nG[h][w]%=self._MOD
        return nG
    def mul(self,A,B):  #行列積  L行M列 * M行N列 = L行N列
        if isinstance(A[0],int): A=[A]
        if isinstance(B[0],int): B=[B]
        assert len(A[0])==len(B),    'cannot calcurate'
        nG=[[0]*max(len(B[i]) for i in range(len(B))) for _ in range(len(A))]
        for h in range(len(nG)):
            for w in range(len(nG[0])):
                for x in range(len(A[0])):
                    nG[h][w]+=A[h][x]*B[x][w]%self._MOD; nG[h][w]%=self._MOD
        return nG


#動作チェック2: yukicoder650 行列木クエリ
N = int(input())
G = [[] for _ in range(N)]
edges = [tuple(map(int, input().split())) for _ in range(N - 1)]
for Ai, Bi in edges:
    G[Ai].append(Bi)
    G[Bi].append(Ai)
HLD = HL_decomposition(N, G)
MP = matrix_pow(10 ** 9 + 7)
ST1 = SegmentTree(N, MP.eye(2), lambda x, y: MP.mul(x, y))
ST2 = SegmentTree(N, MP.eye(2), lambda x, y: MP.mul(y, x))
Q = int(input())
for _ in range(Q):
    t, i, *x = input().split()
    i = int(i)
    x = [int(Xi) for Xi in x]
    if t == 'x':
        Ai, Bi = edges[i]
        ST1.update(HLD.find(Ai, Bi), [[x[0], x[1]], [x[2], x[3]]])
        ST2.update(HLD.find(Ai, Bi), [[x[0], x[1]], [x[2], x[3]]])
    else:
        Lt, Rt = i, x[0]
        to, go, _ = HLD.fold(Lt, Rt)
        assert len(to) == 0
        ans = MP.eye(2)
        for Lt, Rt in to:
            ans = MP.mul(ans, ST2.fold(Lt, Rt))
        for Lt, Rt in go:
            ans = MP.mul(ans, ST1.fold(Lt, Rt))
        print(*[ans[0][0], ans[0][1], ans[1][0], ans[1][1]])
0