結果
問題 | 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 |
ソースコード
#頂点は1-index,下段は0-indexclass LazySegTree:#単位元と結合と作用をここで定義Xunit = (0,0)Aunit = 0def Xf(self,x,y):return (x[0]+y[0],x[1]+y[1])#Xf = maxdef 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 = Nself.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] = xfor 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.Aunitdef propagate_above(self,i):H = i.bit_length() - 1for h in range(H,0,-1):self.propagate_at(i >> h)def recalc_above(self,i):while i > 1:i >>= 1self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1))def update(self,i,x):i += self.Nself.propagate_above(i)self.X[i] = xself.A[i] = self.Aunitself.recalc_above(i)def fold(self,L = 0,R = -1):if R == -1:R = self.NL += self.NR += self.Nself.propagate_above(L // (L & -L))self.propagate_above(R // (R & -R) -1)vL = self.XunitvR = self.Xunitwhile L < R:if L & 1:vL = self.Xf(vL,self.eval_at(L))L += 1if R & 1:R -= 1vR = self.Xf(self.eval_at(R),vR)L >>= 1R >>= 1return self.Xf(vL,vR)def operate_range(self,L,R,x):#区間全体に作用させるL += self.NR += self.NL0 = L // (L & -L)R0 = R // (R & -R) - 1self.propagate_above(L0)self.propagate_above(R0)while L < R:if L & 1:self.A[L] = self.Af(self.A[L],x)L += 1if R & 1:R -= 1self.A[R] = self.Af(self.A[R],x)L >>= 1R >>= 1self.recalc_above(L0)self.recalc_above(R0)def write(self):print(self.X)def change(self,Xf,Xunit,Af,Aunit,operate):self.Xf = Xfself.Xunit = Xunitself.Af = Afself.Aunit = Aunitself.operate = operate#HL分解class HL:#u,vを結ぶpathへのクエリはここにでも# f は区間 [l,r)に対するクエリdef f(self,l,r):passdef merge(self,x,y):return x + ydef __init__(self,G,root):self.G = Gself.root = rootself.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.Gsize = self.sizeH = self.Hwhile stack:now,parent = stack.pop()if now < 0:now = ~now_max = 0for v in G[now]:if v == parent:continuesize[now] += size[v]if size[v] > _max:_max = size[v]H[now] = velse:for v in G[now]:if v == parent:continueself.p[v] = nowstack.append((~v,now))stack.append((v,now))def build_path(self):stack = [(~self.root,-1,self.root),(self.root,-1,self.root)]count = 0G = self.GH = self.Hwhile stack:now,parent,top = stack.pop()if now >= 0:self._in[now] = countcount += 1self.pathtop[now] = toph = H[now]if h is None:continuefor v in G[now]:if v == parent or v == h:continuestack.append((~v,now,v))stack.append((v,now,v))stack.append((~h,now,top))stack.append((h,now,top))else:now = ~nowself.out[now] = count#最近共通先祖def lca(self,a,b):pathtop = self.pathtop_in = self._inpa = 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 bdef subtree_query(self,a,f = None):#if f is None:f = self.freturn 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.mergepathtop = self.pathtopp = self.p_in = self._inpa = pathtop[a]pb = pathtop[b]ans = 0while 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,aans = merge(ans,f(_in[a],_in[b]+1))return ans# a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも#半開区間 [l,r) の集まりを返す#現状順番は適当#こっちのほうが早かったdef path_array(self,a,b):pathtop = self.pathtopp = self.p_in = self._inans = []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,aans.append((_in[a],_in[b]+1))return ansimport sysrr = sys.stdinN = 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)] * Nfor 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 = 0L = hl.path_array(0,ll[0])for l,r in L:ans += seg.fold(l,r)[0]print(ans)