結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 navel_tos
|
| 提出日時 | 2024-02-12 16:34:12 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,021 ms / 2,000 ms |
| コード長 | 7,417 bytes |
| コンパイル時間 | 324 ms |
| コンパイル使用メモリ | 82,552 KB |
| 実行使用メモリ | 129,704 KB |
| 最終ジャッジ日時 | 2024-09-28 18:07:26 |
| 合計ジャッジ時間 | 7,058 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
#yukicoder 650 行列木クエリ
#Heavy-Light decomposition 分解するだけ
class HL_decomposition:
def __init__(self, N, G, root = 0):
#pos[v] = i, order[i] = v 頂点vのDFS順がi番目
#leader[i]: 深さdepth[i]の代表のDFS順 parent[i]: ひとつ根側のDFS順
self._N = N; self._G = G = [[v for v,*_ in S] for S in G] if N > 1 and not isinstance(G[0][0], int) else G; self.pos = pos = [-1] * N; self.order = order = [-1] * N; self.leader = leader = [-1] * N; self.depth = depth = [-1] * N; self.parent = parent = [-1] * N; size = [1] * N; Q = [(root, -1)]
for now,back in Q:
for nxt in G[now]:
if nxt != back: Q.append((nxt, now))
while Q: now,back = Q.pop(); size[back] += size[now] if back != -1 else 0
Q.append((root, -1, 0, -1))
for i in range(N):
now, back, d, t = Q.pop(); pos[now], order[i], parent[i], depth[i] = i, now, pos[back], d; leader[i] = t = t if t != -1 else i
if size[now] > 1:
s, v = 0, now
for nxt in G[now]:
if nxt == back: continue
if s < size[nxt]:
if s > 0: Q.append((v, now, d + 1, -1))
s, v = size[nxt], nxt
else: Q.append((nxt, now, d + 1, -1))
Q.append((v, now, d, t))
def LCA(self, u, v):
i, j = self.pos[u], self.pos[v]; c, d = self.depth[i], self.depth[j]; s, t = self.leader[i], self.leader[j]
for c in range(c - 1, d - 1, -1): i = self.parent[s]; s = self.leader[i]
for d in range(d - 1, c - 1, -1): j = self.parent[t]; t = self.leader[j]
while s != t: i, j = self.parent[s], self.parent[t]; s, t = self.leader[i], self.leader[j]
return self.order[ min(i, j) ]
def find(self, index_u, v = None): #対応する列の添字を返す
return self.pos[index_u] if v == None else max( self.pos[index_u], self.pos[v] )
def rev(self, Lt, Rt = None): #B = A[::-1] A[i], A[Lt,Rt)の対応添字を返す
return self._N - 1 - Lt if Rt == None else (self._N - Rt, self._N - Lt)
def fold(self, u, v):
#u→vパスの作用値順を(to, go, LCA)の順に返す
#to, goともに下から区間作用を行い、最後にf( f(to, A[LCA]), go )を行う
#to: LCA ← uの作用区間[Lt,Rt) x ← f( x, fold(Lt, Rt) ) の順 反転列を使う
#go: LCA → vの作用区間[Lt,Rt) y ← f( fold(Lt, Rt), y ) の順
i, j = self.pos[u], self.pos[v]; c, d = self.depth[i], self.depth[j]; s, t = self.leader[i], self.leader[j]; to, go = [], []
for c in range(c - 1, d - 1, -1): to.append((s, i + 1)); i = self.parent[s]; s = self.leader[i]
for d in range(d - 1, c - 1, -1): go.append((t, j + 1)); j = self.parent[t]; t = self.leader[j]
while s != t: to.append((s, i + 1)); i = self.parent[s]; s = self.leader[i]; go.append((t, j + 1)); j = self.parent[t]; t = self.leader[j]
if i > j: to.append((j + 1, i + 1))
if i < j: go.append((i + 1, j + 1))
return to, go, min(i, j)
#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 not down and t >= X: break
elif down and t <= X: break
else:
cnt = t; now += 1
if now & (now - 1) == 0: return self._n
while now < self._size: #下降
Lt, Rt = self._node[now<<1|0], self._node[now<<1|1]
if not down and self._combine_f(cnt, Lt) >= X: now = now<<1|0
elif down and self._combine_f(cnt, Lt) <= X: now = now<<1|0
else: cnt = self._combine_f(cnt, Lt); now = now<<1|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
#入力受取
N = int(input())
G = [[] for _ in range(N)]
H = []
for _ in range(N - 1):
a,b = map(int,input().split())
G[a].append(b)
G[b].append(a)
H.append((a,b))
#HLDの対応表を作成
mp = matrix_pow(10 ** 9 + 7)
HLD = HL_decomposition(N, G)
#別処理用のSegTreeを作成
ST = SegmentTree(N, [[1,0], [0,1]], mp.mul)
#クエリを処理
for _ in range(int(input())):
t = list(input().split())
if t[0] == 'x':
i,w,x,y,z = map(int, t[1:])
u,v = H[i]
p = HLD.find(u, v)
ST.update(p, [[w,x],[y,z]])
if t[0] == 'g':
u,v = map(int, t[1:])
_, go, _ = HLD.fold(u, v)
#手動で区間作用
ans = [[1,0], [0,1]]
for Lt,Rt in go:
ans = mp.mul(ST.fold(Lt,Rt), ans)
((w,x),(y,z)) = ans
print(w,x,y,z)