結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 navel_tos
|
| 提出日時 | 2024-09-06 13:18:54 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,169 ms / 2,000 ms |
| コード長 | 8,601 bytes |
| コンパイル時間 | 437 ms |
| コンパイル使用メモリ | 82,156 KB |
| 実行使用メモリ | 134,688 KB |
| 最終ジャッジ日時 | 2024-09-06 13:19:02 |
| 合計ジャッジ時間 | 7,964 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 42 ms
55,096 KB |
| testcase_01 | AC | 1,005 ms
106,672 KB |
| testcase_02 | AC | 1,169 ms
134,688 KB |
| testcase_03 | AC | 40 ms
54,984 KB |
| testcase_04 | AC | 1,028 ms
108,052 KB |
| testcase_05 | AC | 1,107 ms
129,376 KB |
| testcase_06 | AC | 41 ms
55,492 KB |
| testcase_07 | AC | 43 ms
56,544 KB |
| testcase_08 | AC | 886 ms
104,260 KB |
| testcase_09 | AC | 1,158 ms
131,372 KB |
| testcase_10 | AC | 40 ms
53,800 KB |
ソースコード
#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))
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]]])
else:
Lt, Rt = i, x[0]
to, go, _ = HLD.fold(Lt, Rt)
assert len(to) == 0
ans = MP.eye(2)
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]])