結果
| 問題 |
No.399 動的な領主
|
| コンテスト | |
| ユーザー |
 山本信二
|
| 提出日時 | 2022-05-29 00:50:22 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,097 bytes |
| コンパイル時間 | 144 ms |
| コンパイル使用メモリ | 13,568 KB |
| 実行使用メモリ | 59,624 KB |
| 最終ジャッジ日時 | 2024-09-20 23:40:03 |
| 合計ジャッジ時間 | 5,642 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 WA * 5 TLE * 1 -- * 12 |
ソースコード
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])
def subtree_array(self,a):
return (self._in[a],self.out[a])
#下のpath_arrayとほぼ同じ。タプルを一つだけ返す
#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
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
class LazyPropSegmentTree:
def __init__(self, lst, op, apply, comp, e, identity):
self.n = len(lst)
self.depth = (self.n - 1).bit_length()
self.N = 1 << self.depth
self.op = op # binary operation of elements
self.apply = apply # function to apply to an element
self.comp = comp # composition of functions
self.e = e # identity element w.r.t. op
self.identity = identity # identity element w.r.t. comp
self.v, self.length = self._build(lst) # self.v is set to be 1-indexed for simplicity
self.lazy = [self.identity] * (2 * self.N)
def __getitem__(self, i):
return self.fold(i, i+1)
def _build(self, lst):
# construction of a tree
# total 2 * self.N elements (tree[0] is not used)
e, N, op = self.e, self.N, self.op
tree = [e] * N + lst + [e] * (N - self.n)
length = [1] * (2 * N)
for i in range(N - 1, 0, -1):
lc, rc = i << 1, (i << 1)|1
tree[i] = op(tree[lc], tree[rc])
length[i] = length[lc] + length[rc]
return tree, length
def _indices(self, l, r):
left = l + self.N; right = r + self.N
left //= (left & (-left)); right //= (right & (-right))
left >>= 1; right >>= 1
while left != right:
if left > right: yield left; left >>= 1
else: yield right; right >>= 1
while left > 0: yield left; left >>= 1
# propagate self.lazy and self.v in a top-down manner
def _propagate_topdown(self, *indices):
identity, v, lazy, length, apply, comp = self.identity, self.v, self.lazy, self.length, self.apply, self.comp
for k in reversed(indices):
x = lazy[k]
if x == identity: continue
lc, rc = k << 1, (k << 1) | 1
lazy[lc] = comp(lazy[lc], x)
lazy[rc] = comp(lazy[rc], x)
v[lc] = apply(v[lc], x, length[lc])
v[rc] = apply(v[rc], x, length[rc])
lazy[k] = identity # propagated
# propagate self.v in a bottom-up manner
def _propagate_bottomup(self, indices):
v, op = self.v, self.op
for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])
# update for the query interval [l, r) with function x
def update(self, l, r, x):
*indices, = self._indices(l, r)
self._propagate_topdown(*indices)
N, v, lazy, length, apply, comp = self.N, self.v, self.lazy, self.length, self.apply, self.comp
# update self.v and self.lazy for the query interval [l, r)
left = l + N; right = r + N
if left & 1: v[left] = apply(v[left], x, length[left]); left += 1
if right & 1: right -= 1; v[right] = apply(v[right], x, length[right])
left >>= 1; right >>= 1
while left < right:
if left & 1:
lazy[left] = comp(lazy[left], x)
v[left] = apply(v[left], x, length[left])
left += 1
if right & 1:
right -= 1
lazy[right] = comp(lazy[right], x)
v[right] = apply(v[right], x, length[right])
left >>= 1; right >>= 1
self._propagate_bottomup(indices)
# returns answer for the query interval [l, r)
def fold(self, l, r):
self._propagate_topdown(*self._indices(l, r))
e, N, v, op = self.e, self.N, self.v, self.op
# calculate the answer for the query interval [l, r)
left = l + N; right = r + N
L = R = e
while left < right:
if left & 1: # self.v[left] is the right child
L = op(L, v[left])
left += 1
if right & 1: # self.v[right-1] is the left child
right -= 1
R = op(v[right], R)
left >>= 1; right >>= 1
return op(L, R)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
a,b = map(int,input().split())
G[a-1].append(b-1)
G[b-1].append(a-1)
hl = HL(G,1)
"""
print(hl._in)
print(hl.p)
print(hl.pathtop)
"""
Q = int(input())
seq = [1] * N
op = lambda x, y: x+y
apply = lambda x, f, l: x + f*l
comp = lambda f, g: f + g
e = 0
identity = 0
A = seq
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
*arg, = map(int, input().split())
s, t= arg
lpsg.update(s-1, t, 1)
ans.append(lpsg.fold(s-1, t))
print(sum(ans))