結果

問題 No.900 aδδitivee
ユーザー ああいい
提出日時 2022-03-04 20:54:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 999 ms / 2,000 ms
コード長 8,092 bytes
コンパイル時間 704 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 140,932 KB
最終ジャッジ日時 2024-07-18 18:19:25
合計ジャッジ時間 21,188 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#1-index,0-index
class LazySegTree:
#
Xunit = (0,0)
Aunit = 0
def Xf(self,x,y):
return (x[0]+y[0],x[1]+y[1])
#Xf = max
def Af(self,a,b):
return a + b
#AX
def operate(self,x,a):
return (x[0] + x[1] * a,x[1])
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,vpath
# 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 = [0] * self.N #
self.H = [None] * self.N #Heavy_edgeNone
self._in = [-1] * self.N #
self.out = [-1] * self.N #
# [_in[i],out[i]) i
self.pathtop = [0] * self.N #ipath
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])
def subtree_array(self,a):
return (self._in[a],self.out[a])
#path_array
#f = lambda l,r:seg.fold(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
# a,b path便
# [l,r)
#
#
def path_array(self,a,b):
pathtop = self.pathtop
p = self.p
_in = self._in
ans = []
pa = pathtop[a]
pb = pathtop[b]
while pa != pb:
if _in[pa] > _in[pb]:
ans.append((_in[pa],_in[a]+1))
a = p[pa]
pa = pathtop[a]
else:
ans.append((_in[pb],_in[b]+1))
b = p[pb]
pb = pathtop[b]
if _in[a] > _in[b]:
a,b = b,a
ans.append((_in[a],_in[b]+1))
return ans
import sys
rr = sys.stdin
N = int(rr.readline())
G = [[] for _ in range(N)]
edge = []
for _ in range(N-1):
u,v,w = map(int,rr.readline().split())
G[u].append(v)
G[v].append(u)
edge.append((u,v,w))
hl = HL(G,0)
seg = LazySegTree(N)
seq = [(0,0)] * N
for u,v,w in edge:
if hl.p[u] == v:
seq[hl._in[u]] = (w,1)
else:
seq[hl._in[v]] = (w,1)
seg.build(seq)
Q = int(rr.readline())
for _ in range(Q):
t,*ll = map(int,rr.readline().split())
if t == 1:
l,r = hl.subtree_array(ll[0])
seg.operate_range(l+1,r,ll[1])
else:
ans = 0
L = hl.path_array(0,ll[0])
for l,r in L:
ans += seg.fold(l,r)[0]
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0