結果
| 問題 | No.1790 Subtree Deletion |
| ユーザー |
 ああいい
|
| 提出日時 | 2022-02-26 11:07:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 830 ms / 3,000 ms |
| コード長 | 7,936 bytes |
| コンパイル時間 | 152 ms |
| コンパイル使用メモリ | 82,496 KB |
| 実行使用メモリ | 115,504 KB |
| 最終ジャッジ日時 | 2024-07-04 06:41:59 |
| 合計ジャッジ時間 | 10,859 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 40 ms
53,888 KB |
| testcase_01 | AC | 42 ms
53,760 KB |
| testcase_02 | AC | 44 ms
53,504 KB |
| testcase_03 | AC | 825 ms
115,504 KB |
| testcase_04 | AC | 739 ms
113,848 KB |
| testcase_05 | AC | 822 ms
114,860 KB |
| testcase_06 | AC | 830 ms
113,848 KB |
| testcase_07 | AC | 816 ms
113,708 KB |
| testcase_08 | AC | 324 ms
78,488 KB |
| testcase_09 | AC | 737 ms
112,440 KB |
| testcase_10 | AC | 759 ms
114,088 KB |
| testcase_11 | AC | 771 ms
114,236 KB |
| testcase_12 | AC | 568 ms
111,960 KB |
| testcase_13 | AC | 638 ms
107,204 KB |
| testcase_14 | AC | 406 ms
86,464 KB |
ソースコード
#頂点は1-index,下段は0-index
class LazySegTree:
#単位元と結合と作用をここで定義
Xunit = 0
Aunit = 1
def Xf(self,x,y):
return x^y
#Xf = max
def Af(self,a,b):
return a * b
#AのXへの作用
def operate(self,x,a):
return x * a
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
def path_array(self,a,b):
# a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも
#半開区間 [l,r) の集まりを返す
#現状順番は適当
#こっちのほうが早かった
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+1)]
edge = []
for _ in range(N-1):
l,r,a = map(int,input().split())
G[l].append(r)
G[r].append(l)
edge.append((l,r,a))
hl = HL(G,1)
seg = LazySegTree(N)
dp = [0] * N
for l,r,a in edge:
if hl.p[l] == r:
dp[hl._in[l]] = a
else:
dp[hl._in[r]] = a
seg.build(dp)
Q = int(rr.readline())
for _ in range(Q):
t,x = map(int,input().split())
if t == 1:
l,r = hl.subtree_array(x)
seg.operate_range(l,r,0)
else:
l,r = hl.subtree_array(x)
print(seg.fold(l+1,r))