結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 37 ms
53,760 KB |
| testcase_01 | AC | 36 ms
54,272 KB |
| testcase_02 | AC | 46 ms
65,120 KB |
| testcase_03 | AC | 45 ms
65,152 KB |
| testcase_04 | AC | 46 ms
64,896 KB |
| testcase_05 | AC | 45 ms
64,768 KB |
| testcase_06 | AC | 47 ms
66,176 KB |
| testcase_07 | AC | 834 ms
140,416 KB |
| testcase_08 | AC | 860 ms
140,548 KB |
| testcase_09 | AC | 851 ms
140,040 KB |
| testcase_10 | AC | 851 ms
140,664 KB |
| testcase_11 | AC | 852 ms
140,280 KB |
| testcase_12 | AC | 830 ms
140,932 KB |
| testcase_13 | AC | 833 ms
140,036 KB |
| testcase_14 | AC | 876 ms
140,796 KB |
| testcase_15 | AC | 850 ms
139,768 KB |
| testcase_16 | AC | 903 ms
140,928 KB |
| testcase_17 | AC | 836 ms
140,148 KB |
| testcase_18 | AC | 810 ms
140,140 KB |
| testcase_19 | AC | 930 ms
140,028 KB |
| testcase_20 | AC | 999 ms
140,424 KB |
| testcase_21 | AC | 903 ms
140,668 KB |
| testcase_22 | AC | 572 ms
120,532 KB |
| testcase_23 | AC | 569 ms
121,260 KB |
| testcase_24 | AC | 518 ms
119,576 KB |
| testcase_25 | AC | 545 ms
120,608 KB |
| testcase_26 | AC | 503 ms
119,052 KB |
| testcase_27 | AC | 521 ms
119,816 KB |
| testcase_28 | AC | 576 ms
120,736 KB |
ソースコード
#頂点は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
#AのXへの作用
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,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 = [0] * 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])
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)