Day 050-Q4 | HLD + 行列積モノイド SegTree（木パス行列積クエリ）

問題

$N$ 頂点の根付き木（根は頂点1）があり、各頂点 $v$ には $2 \times 2$ 整数行列 $M_v$ が付いている。次の $Q$ 個のクエリを処理せよ。

クエリ1: 1 v a b c d — 頂点 $v$ の行列を $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ に更新する。
クエリ2: 2 u v — 頂点 $u$ から $v$ へのパス上の行列積（$u$ 側から順）を $\bmod 10^9+7$ で求め、積行列の $(1,1)$ 成分を出力する。

制約

$1 \le N, Q \le 10^5$

$0 \le a,b,c,d \le 10^9$

時間制限: 4秒

入出力例

入力例 1

5 3
1 0 0 1
2 1 0 2
1 1 1 0
0 1 1 1
3 0 0 3
1 2
1 3
2 4
2 5
2 1 4
1 3 1 2 3 4
2 1 4

出力例 1

2
2

クエリ 2 1 4: パス $1 \to 2 \to 4$、積 $M_1 \cdot M_2 \cdot M_4 \bmod 10^9+7$ の $(1,1)$ 成分。

概念図: HLD によるパス分解と行列積

ヒント（段階的開示）

ヒント1: 方向性

HLD で木のパスを $O(\log N)$ 個の連続区間に分解し、各区間の行列積をセグメント木で管理する。

ヒント2: アプローチ

HLD で各頂点に連続した位置 pos[v] を割り当て
SegTree の各ノードに区間の行列積（左→右）を保持
パスクエリ: $u, v$ 側から LCA まで遡りながら行列積を収集
行列積は非可換なので $u \to v$ の方向を厳密に管理

ヒント3: 2×2行列積モノイドの実装

MOD = 10**9 + 7
IDENT = [[1,0],[0,1]]

def mat_mul(A, B):
    return [
        [(A[0][0]*B[0][0]+A[0][1]*B[1][0])%MOD,
         (A[0][0]*B[0][1]+A[0][1]*B[1][1])%MOD],
        [(A[1][0]*B[0][0]+A[1][1]*B[1][0])%MOD,
         (A[1][0]*B[0][1]+A[1][1]*B[1][1])%MOD]
    ]

# HLD パスクエリ(左側と右側を分けて管理)
left_parts = []   # u側 - 後で逆順に積む
right_parts = []  # v側 - 正順に積む

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

MOD = 10**9 + 7
IDENT = [[1,0],[0,1]]

def mat_mul(A, B):
    return [[(A[0][0]*B[0][0]+A[0][1]*B[1][0])%MOD,(A[0][0]*B[0][1]+A[0][1]*B[1][1])%MOD],
            [(A[1][0]*B[0][0]+A[1][1]*B[1][0])%MOD,(A[1][0]*B[0][1]+A[1][1]*B[1][1])%MOD]]

class SegTree:
    def __init__(self, n):
        self.n = n; self.sz = 1
        while self.sz < n: self.sz <<= 1
        self.data = [[row[:] for row in IDENT] for _ in range(2*self.sz)]

    def update(self, i, m):
        i += self.sz; self.data[i] = m; i >>= 1
        while i >= 1:
            self.data[i] = mat_mul(self.data[2*i], self.data[2*i+1]); i >>= 1

    def query(self, l, r):
        rl = [row[:] for row in IDENT]; rr = [row[:] for row in IDENT]
        l += self.sz; r += self.sz + 1
        while l < r:
            if l&1: rl = mat_mul(rl, self.data[l]); l += 1
            if r&1: r -= 1; rr = mat_mul(self.data[r], rr)
            l >>= 1; r >>= 1
        return mat_mul(rl, rr)

def solve():
    N, Q = map(int, input().split())
    mats = [[list(map(int,input().split())) for _ in range(2)] if False else None for _ in range(N)]
    mats = []
    for _ in range(N):
        a,b,c,d = map(int,input().split())
        mats.append([[a%MOD,b%MOD],[c%MOD,d%MOD]])
    adj = defaultdict(list)
    for _ in range(N-1):
        u,v = map(int,input().split())
        adj[u].append(v); adj[v].append(u)

    # HLD
    par=[0]*(N+1); dep=[0]*(N+1); sz=[1]*(N+1); heavy=[-1]*(N+1)
    head=[0]*(N+1); pos=[0]*(N+1); order=[]
    # DFS1: sz, heavy
    stk=[(1,-1,False)]
    while stk:
        v,p,done=stk.pop()
        if done:
            mx,hc=0,-1
            for u in adj[v]:
                if u!=par[v]: sz[v]+=sz[u]; (mx:=sz[u]) and hc==(hc:=u) if sz[u]>mx else None
            # cleaner:
            mx=0
            for u in adj[v]:
                if u!=par[v]:
                    sz[v]+=sz[u]
                    if sz[u]>mx: mx=sz[u]; heavy[v]=u
        else:
            par[v]=p; stk.append((v,p,True))
            for u in adj[v]:
                if u!=p: dep[u]=dep[v]+1; stk.append((u,v,False))
    # DFS2: head, pos
    timer=[0]; stk2=[(1,1)]
    while stk2:
        v,h=stk2.pop()
        head[v]=h; pos[v]=timer[0]; order.append(v); timer[0]+=1
        for u in adj[v]:
            if u!=par[v] and u!=heavy[v]: stk2.append((u,u))
        if heavy[v]!=-1: stk2.append((heavy[v],h))

    seg=SegTree(N)
    for v in range(1,N+1): seg.update(pos[v],mats[v-1])

    out=[]
    for _ in range(Q):
        line=list(map(int,input().split()))
        if line[0]==1:
            v=line[1]; a,b,c,d=line[2],line[3],line[4],line[5]
            seg.update(pos[v],[[a%MOD,b%MOD],[c%MOD,d%MOD]])
        else:
            u,v=line[1],line[2]
            left_p=[]; right_p=[]
            while head[u]!=head[v]:
                if dep[head[u]]dep[v]: u,v=v,u; left_p,right_p=right_p,left_p
            right_p.append(seg.query(pos[u],pos[v]))
            res=[row[:] for row in IDENT]
            for m in left_p: res=mat_mul(m,res)
            for m in reversed(right_p): res=mat_mul(res,m)
            out.append(res[0][0])
    print('\n'.join(map(str,out)))

solve()

Step-by-Step 解説

1HLD の構築
DFS1 でサイズ計算と heavy child 決定（最大サイズの子）。DFS2 で heavy edge を優先訪問して連続した $pos$ を割り当て、チェーンのトップ $head[v]$ を記録。

2行列積 SegTree
モノイド演算 = 行列積（$\bmod 10^9+7$）の SegTree。区間積は左→右の順。$2 \times 2$ 行列で定数倍8の乗算が発生。

3パスクエリの方向管理
行列積は非可換。$u \to v$ の方向を保つため: $v$ 側（LCA 近傍）を順方向で収集 → $right\_parts$。$u$ 側（LCA から遠い）を逆方向で積む → $left\_parts$。

4更新クエリ
頂点 $v$ の行列更新 → seg.update(pos[v], new_mat) のみ。$O(\log N)$。

5計算量
HLD で $O(\log N)$ チェーン、各チェーン内 SegTree クエリ $O(\log N)$、行列積 $O(8)$ → クエリ全体 $O(\log^2 N \cdot 8)$。

計算量

構築: $O(N \log N)$
更新クエリ: $O(\log N)$
パスクエリ: $O(\log^2 N)$（HLD $O(\log N)$ チェーン × SegTree $O(\log N)$）
空間: $O(N)$（SegTree の行列格納で定数倍8）

よくあるミス

ミス	原因	正しい書き方
パスの方向を無視	行列積は非可換	left/right を分けて管理し最後に正しく結合
HLD の pos 割り当てミス	スタック順序で heavy が遅れる	light child を先に push し heavy を最後に処理
SegTree の区間が 0/1-indexed 混在	オフバイワン	pos は 0-indexed、SegTree も 0-indexed で統一
単位行列を省略	空の積が返せない	`IDENT = [[1,0],[0,1]]` を常に初期値として使用

次のステップ

発展問題: 辺に行列が付いた木で「辺の更新」も可能にする（辺を頂点に変換するテクニック）
関連: 3×3 以上の行列や複数 mod への拡張
応用: HLD + 遅延 SegTree で「区間に行列変換を適用」するクエリ

自己評価

完全理解おおむね理解要復習