結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 ああいい
|
| 提出日時 | 2022-02-25 12:53:14 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 4,083 ms / 10,000 ms |
| コード長 | 7,348 bytes |
| コンパイル時間 | 279 ms |
| コンパイル使用メモリ | 82,280 KB |
| 実行使用メモリ | 141,516 KB |
| 最終ジャッジ日時 | 2024-07-03 06:29:08 |
| 合計ジャッジ時間 | 16,271 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4,083 ms
140,376 KB |
| testcase_01 | AC | 2,973 ms
141,516 KB |
| testcase_02 | AC | 3,948 ms
140,668 KB |
ソースコード
#頂点は1-index,下段は0-index
class LazySegTree:
#単位元と結合と作用をここで定義
Xunit = 0
Aunit = 0
def Xf(self,x,y):
a,b = unpack(x)
c,d = unpack(y)
return pack((a+c)%P,(b+d)%P)
#Xf = max
def Af(self,a,b):
return (a + b)%P
#AのXへの作用
def operate(self,x,a):
s,t = unpack(x)
return pack((s + t * a)%P,t)
def __init__(self,N):
self.N = N
self.X = [self.Xunit] * (N + N)
self.A = [self.Aunit] * (N + N)
def build(self,seq):
for i,x in enumerate(seq,self.N):
self.X[i] = x
for i in range(self.N-1,0,-1):
self.X[i] = self.Xf(self.X[i<<1],self.X[i<<1 | 1])
def eval_at(self,i):
return self.operate(self.X[i],self.A[i])
def propagate_at(self,i):
self.X[i] = self.eval_at(i)
self.A[i<<1] = self.Af(self.A[i<<1],self.A[i])
self.A[i<<1 | 1] = self.Af(self.A[i<<1 | 1],self.A[i])
self.A[i] = self.Aunit
def propagate_above(self,i):
H = i.bit_length() - 1
for h in range(H,0,-1):
self.propagate_at(i >> h)
def recalc_above(self,i):
while i > 1:
i >>= 1
self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
def update(self,i,x):
i += self.N
self.propagate_above(i)
self.X[i] = x
self.A[i] = self.Aunit
self.recalc_above(i)
def fold(self,L = 0,R = -1):
if R == -1:R = self.N
L += self.N
R += self.N
self.propagate_above(L // (L & -L))
self.propagate_above(R // (R & -R) -1)
vL = self.Xunit
vR = self.Xunit
while L < R:
if L & 1:
vL = self.Xf(vL,self.eval_at(L))
L += 1
if R & 1:
R -= 1
vR = self.Xf(self.eval_at(R),vR)
L >>= 1
R >>= 1
return self.Xf(vL,vR)
def operate_range(self,L,R,x):
#区間全体に作用させる
L += self.N
R += self.N
L0 = L // (L & -L)
R0 = R // (R & -R) - 1
self.propagate_above(L0)
self.propagate_above(R0)
while L < R:
if L & 1:
self.A[L] = self.Af(self.A[L],x)
L += 1
if R & 1:
R -= 1
self.A[R] = self.Af(self.A[R],x)
L >>= 1
R >>= 1
self.recalc_above(L0)
self.recalc_above(R0)
def write(self):
print(self.X)
def change(self,Xf,Xunit,Af,Aunit,operate):
self.Xf = Xf
self.Xunit = Xunit
self.Af = Af
self.Aunit = Aunit
self.operate = operate
#HL分解
class HL:
#u,vを結ぶpathへのクエリはここにでも
# f は区間 [l,r)に対するクエリ
def f(self,l,r):
pass
def merge(self,x,y):
return x + y
def __init__(self,G,root):
self.G = G
self.root = root
self.N = len(G)
self.size = [1] * self.N #部分木のサイズ
self.p = [-1] * self.N #親頂点
self.H = [None] * self.N #Heavy_edgeでつながる子頂点。葉ではNoneが入ってる
self._in = [-1] * self.N #最初に探索したときの位置
self.out = [-1] * self.N #部分木をでるタイミング。オイラーとはちょっと違う。
#開区間 [_in[i],out[i]) がiの部分木に対応
self.pathtop = [0] * self.N #iの属するpathの中で最も根に近い頂点。代表にする
self.build()
self.build_path()
def build(self):
stack = [(~self.root,-1),(self.root,-1)]
G = self.G
size = self.size
H = self.H
while stack:
now,parent = stack.pop()
if now < 0:
now = ~now
_max = 0
for v in G[now]:
if v == parent:continue
size[now] += size[v]
if size[v] > _max:
_max = size[v]
H[now] = v
else:
for v in G[now]:
if v == parent:continue
self.p[v] = now
stack.append((~v,now))
stack.append((v,now))
def build_path(self):
stack = [(~self.root,-1,self.root),(self.root,-1,self.root)]
count = 0
G = self.G
H = self.H
while stack:
now,parent,top = stack.pop()
if now >= 0:
self._in[now] = count
count += 1
self.pathtop[now] = top
h = H[now]
if h is None:continue
for v in G[now]:
if v == parent or v == h:continue
stack.append((~v,now,v))
stack.append((v,now,v))
stack.append((~h,now,top))
stack.append((h,now,top))
else:
now = ~now
self.out[now] = count
def lca(self,a,b):
#最近共通先祖
pathtop = self.pathtop
_in = self._in
pa = pathtop[a]
pb = pathtop[b]
while pa != pb:
if _in[pa] > _in[pb]:
a = self.p[pa]
pa = pathtop[a]
else:
b = self.p[pb]
pb = pathtop[b]
return a if _in[a] < _in[b] else b
def subtree_query(self,a,f = None):
#if f is None:f = self.f
return f(self._in[a],self.out[a])
#f = lambda l,r:seg.flod(l,r) とか
#f = lambda l,r:seg.oparete_range(l,r,x) とか
#代入して使う
def path_query(self,a,b,f = None,merge = None):
#if f is None:f = self.f
#if merge is None:merge = self.merge
pathtop = self.pathtop
p = self.p
_in = self._in
pa = pathtop[a]
pb = pathtop[b]
ans = 0
while pa != pb:
if _in[pa] > _in[pb]:
ans = merge(ans,f(_in[pa],_in[a]+1))
a = p[pa]
pa = pathtop[a]
else:
ans = merge(ans,f(_in[pb],_in[b]+1))
b = p[pb]
pb = pathtop[b]
if _in[a] > _in[b]:
a,b = b,a
ans = merge(ans,f(_in[a],_in[b]+1))
return ans
N = int(input())
S = list(map(int,input().split()))
C = list(map(int,input().split()))
G = [[] for _ in range(N+1)]
P = 10 ** 9 + 7
for _ in range(N-1):
a,b = map(int,input().split())
G[a].append(b)
G[b].append(a)
hl = HL(G,1)
"""
print(hl._in)
print(hl.p)
print(hl.pathtop)
"""
def pack(a,b):
return (a << 30) + b
def unpack(x):
return (x >> 30,x & ((1 << 30)-1))
seg = LazySegTree(N)
seq = [0] * N
for i in range(1,N+1):
seq[hl._in[i]] = pack(S[i-1],C[i-1])
seg.build(seq)
Q = int(input())
for _ in range(Q):
t,*l = map(int,input().split())
if t == 0:
x,y,z = l
hl.path_query(x,y,lambda l,r:seg.operate_range(l,r,z),merge = lambda x,y:0)
else:
x,y = l
f = lambda l,r:unpack(seg.fold(l,r))[0]
merge = lambda x,y:(x+y)%P
print(hl.path_query(x,y,f,merge))