結果
| 問題 |
No.2439 Fragile Apple Tree
|
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2023-08-15 04:33:56 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 15,028 bytes |
| コンパイル時間 | 211 ms |
| コンパイル使用メモリ | 82,336 KB |
| 実行使用メモリ | 581,704 KB |
| 最終ジャッジ日時 | 2024-11-23 08:30:43 |
| 合計ジャッジ時間 | 138,599 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 TLE * 3 MLE * 3 |
ソースコード
"""Buggy! the output of practice_k becomes about 1/4."""
from typing import Callable, List, TypeVar
S = TypeVar("S")
F = TypeVar("F")
MOD = 998244353
class LazySegmentTree:
"""Lazy Segment Tree
References:
https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
"""
__slots__ = [
"e",
"op",
"id",
"mapping",
"composition",
"_n",
"_log",
"_size",
"tree",
"lazy",
]
def __init__(
self,
a: List[S],
e: S,
op: Callable[[S, S], S],
id_: F,
mapping: Callable[[F, S], S],
composition: Callable[[F, F], F],
) -> None:
self.e = e
self.op = op
self.id = id_
self.mapping = mapping
self.composition = composition
self._n = len(a)
self._log = (self._n - 1).bit_length()
self._size = 1 << self._log
self.tree = [e] * self._size + a + [e] * (self._size - self._n)
for i in range(self._size - 1, 0, -1):
self._update(i)
self.lazy = [id_] * self._size
def _update(self, k: int) -> None:
"""Update the value of a[k]."""
self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])
def _apply_all(self, k: int, f: F) -> None:
self.tree[k] = self.mapping(f, self.tree[k])
if k < self._size:
self.lazy[k] = self.composition(f, self.lazy[k])
def _push(self, k: int) -> None:
self._apply_all(2 * k, self.lazy[k])
self._apply_all(2 * k + 1, self.lazy[k])
self.lazy[k] = self.id
def set(self, k: int, x: S) -> None:
"""Assign x to a[k] in O(log n)."""
assert 0 <= k < self._n
k += self._size
for i in range(self._log, 0, -1):
self._push(k >> i)
self.tree[k] = x
while k:
k >>= 1
self._update(k)
def get(self, k: int) -> S:
"""Return a[k] in O(1)."""
assert 0 <= k < self._n
k += self._size
for i in range(self._log, 0, -1):
self._push(k >> i)
return self.tree[k]
def prod(self, l: int, r: int) -> S:
"""Return op(a[l], ..., a[r - 1]). Return e, if l == r.
Complexity: O(log n)
"""
assert 0 <= l <= r <= self._n
if l == r:
return self.e
l += self._size
r += self._size
for i in range(self._log, 0, -1):
if ((l >> i) << i) != l:
self._push(l >> i)
if ((r >> i) << i) != r:
self._push(r >> i)
sml, smr = self.e, self.e
while l < r:
if l & 1:
sml = self.op(sml, self.tree[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.tree[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def prod_all(self) -> S:
"""Return op(a[0], ..., a[n - 1]. Return e if n == 0.
Complexity: O(1)
"""
return self.tree[1]
def apply(self, k: int, f: F) -> None:
"""Apply a[p] = op_st(a[p], x) in O(log n)."""
assert 0 <= k < self._n
k += self._size
for i in range(self._log, 0, -1):
self._push(k >> i)
self.tree[k] = self.mapping(f, self.tree[k])
for i in range(1, self._log + 1):
self._update(k >> i)
def apply_range(self, l: int, r: int, f: F) -> None:
"""Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
assert 0 <= l <= r <= self._n
if l == r:
return
l += self._size
r += self._size
for i in range(self._log, 0, -1):
if ((l >> i) << i) != l:
self._push(l >> i)
if ((r >> i) << i) != r:
self._push((r - 1) >> i)
l_tmp, r_tmp = l, r
while l < r:
if l & 1:
self._apply_all(l, f)
l += 1
if r & 1:
r -= 1
self._apply_all(r, f)
l >>= 1
r >>= 1
l, r = l_tmp, r_tmp
for i in range(1, self._log + 1):
if ((l >> i) << i) != l:
self._update(l >> i)
if ((r >> i) << i) != r:
self._update((r - 1) >> i)
def max_right(self, l: int, g: Callable[[S], bool]) -> int:
"""
Return an index r satisfying both:
1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false.
If f is monotone, this is the maximum r satisfying:
f(op(a[l], a[l + 1], ..., a[r - 1])) = true.
Complexity: O(log n)
"""
assert 0 <= l <= self._n
assert g(self.e)
if l == self._n:
return self._n
l += self._size
for i in range(self._log, 0, -1):
self._push(l >> i)
sm = self.e
while True:
while not l & 1:
l >>= 1
if not g(self.op(sm, self.tree[l])):
while l < self._size:
l *= 2
if g(self.op(sm, self.tree[l])):
sm = self.op(sm, self.tree[l])
l += 1
return l - self._size
sm = self.op(sm, self.tree[l])
l += 1
if (l & -l) == l:
break
return self._n
def min_left(self, r: int, g: Callable[[S], bool]) -> int:
"""
Return an index l satisfying both:
1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false.
If f is monotone, this is the minimum l satisfying:
f(op(a[l], a[l + 1], ..., a[r - 1])) = true.
Complexity: O(log n)
"""
assert 0 <= r <= self._n
assert g(self.e)
if not r:
return 0
r += self._size
for i in range(self._log, 0, -1):
self._push((r - 1) >> i)
sm = self.e
while True:
r -= 1
while r > 1 and r & 1:
r >>= 1
if not g(self.op(self.tree[r], sm)):
while r < self._size:
r = 2 * r + 1
if g(self.op(self.tree[r], sm)):
sm = self.op(self.tree[r], sm)
r -= 1
return r + 1 - self._size
sm = self.op(self.tree[r], sm)
if (r & -r) == r:
break
return 0
def min_left(self,r,g):
assert (0<=r and r<=self._n)
assert g(self.e)
if r==0:return 0
r+=self._size
for i in range(self._log,0,-1):self._push((r-1)>>i)
sm=self.e
while(1):
r-=1
while(r>1 and (r%2)):r>>=1
if not(g(self.op(self.tree[r],sm))):
while(r<self._size):
self._push(r)
r=(2*r+1)
if g(self.op(self.tree[r],sm)):
sm=self.op(self.tree[r],sm)
r-=1
return r+1-self._size
sm=self.op(self.tree[r],sm)
if (r&-r)==r:break
return 0
def nibutan_query(self, l, r) -> int:
if self.prod(l, r) > 0:
return -1
res = self.min_left(r, lambda x:x>0)
return res-1
class DualSegmentTree:
def __init__(self, size, f, default):
self.n = (size-1).bit_length()
self.size = 1<<self.n
self.default = default
self.lazy = [default]*(self.size*2)
self.f = f
def propagate(self, k):
lazy = self.lazy
if lazy[k] != self.default:
lazy[2*k] = self.f(lazy[2*k], lazy[k])
lazy[2*k+1] = self.f(lazy[2*k+1], lazy[k])
lazy[k] = self.default
def thrust(self, k):
for i in range(self.n,0,-1):
self.propagate(k>>i)
def update(self, a, b, x):
a += self.size
b += self.size-1
self.thrust(a)
self.thrust(b)
l = a
r = b + 1
lazy = self.lazy
while l < r:
if l & 1:
lazy[l] = self.f(lazy[l], x)
l += 1
if r & 1:
r -= 1
lazy[r] = self.f(lazy[r], x)
l >>= 1
r >>= 1
def get(self, k):
k += self.size
self.thrust(k)
return self.lazy[k]
class HLD:
def __init__(self, n):
self.g = [[] for _ in range(n)]
self.sz = [1] * n
self.in_ = [0] * n
self.out = [0] * n
self.head = [0] * n
self.rev = [0] * n
self.par = [0] * n
self.dep = [0] * n
def dfs_sz(self, a, p, b):
self.par[a] = p
self.sz[a] = 1
self.dep[a] = b
if self.g[a] and self.g[a][0] == p:
self.g[a][0], self.g[a][-1] = self.g[a][-1], self.g[a][0]
for to in self.g[a]:
if to == p:
continue
self.dfs_sz(to, a, b + 1)
self.sz[a] += self.sz[to]
if self.sz[self.g[a][0]] < self.sz[to]:
self.g[a][0], to = to, self.g[a][0]
def dfs_hld(self, a, p, t):
self.in_[a] = t[0]
self.rev[t[0]] = a
t[0] += 1
for to in self.g[a]:
if to == p:
continue
self.head[to] = self.head[a] if self.g[a][0] == to else to
self.dfs_hld(to, a, t)
self.out[a] = t[0]
def dfs_sz(self, v):
stack = [v]
while stack:
v = stack.pop()
if v >= 0:
if len(self.g[v]) >= 2 and self.g[v][-1] == self.par[v]:
self.g[v][-1], self.g[v][-2] = self.g[v][-2], self.g[v][-1]
for i, nv in enumerate(self.g[v]):
if nv == self.par[v]:
continue
self.dep[nv] = self.dep[v] + 1
self.par[nv] = v
stack.append(i)
stack.append(~nv)
stack.append(nv)
else:
nv = ~v
v = self.par[nv]
i = stack.pop()
self.sz[v] += self.sz[nv]
if self.sz[nv] > self.sz[self.g[v][-1]]:
self.g[v][-1], self.g[v][i] = self.g[v][i], self.g[v][-1]
def dfs_hld(self, v):
id = 0
stack = [~v, v]
while stack:
v = stack.pop()
if v >= 0:
self.in_[v] = id
id += 1
for nv in self.g[v]:
if nv == self.par[v]:
continue
if nv == self.g[v][-1]:
self.head[nv] = self.head[v]
else:
self.head[nv] = nv
stack.append(~nv)
stack.append(nv)
else:
self.out[~v] = id
for i in range(len(self.g)):
self.rev[self.in_[i]] = i
def edgeset(self, a, b):
self.g[a].append(b)
self.g[b].append(a)
def build(self):
self.dfs_sz(0)
self.dfs_hld(0)
def input(self, n):
for _ in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
self.edgeset(a, b)
self.build()
def la(self, a, x):
while True:
h = self.head[a]
if self.in_[a] - x >= self.in_[h]:
return self.rev[self.in_[a] - x]
x -= self.in_[a] - self.in_[h] + 1
a = self.par[h]
def lca(self, a, b):
while True:
if self.in_[a] > self.in_[b]:
a, b = b, a
if self.head[a] == self.head[b]:
return a
b = self.par[self.head[b]]
def query(self, a, b, ti, q, f, edge=False):
l = ti
r = ti
while True:
if self.in_[a] > self.in_[b]:
a, b = b, a
l, r = r, l
if self.head[a] == self.head[b]:
break
l = f(q(self.in_[self.head[b]], self.in_[b] + 1), l)
b = self.par[self.head[b]]
return f(f(q(self.in_[a] + edge, self.in_[b] + 1), l), r)
def nibutan(self, a, b, q, edge=False):
while True:
if self.in_[a] > self.in_[b]:
a, b = b, a
if self.head[a] == self.head[b]:
break
res = q(self.in_[self.head[b]], self.in_[b] + 1)
if res != -1:
return self.rev[res]
b = self.par[self.head[b]]
res = q(self.in_[a] + edge, self.in_[b] + 1)
if res != -1:
return self.rev[res]
return -1
def addpath(self, a, b, x, q, edge=False):
while True:
if self.in_[a] > self.in_[b]:
a, b = b, a
if self.head[a] == self.head[b]:
break
q(self.in_[self.head[b]], self.in_[b] + 1, x)
b = self.par[self.head[b]]
q(self.in_[a] + edge, self.in_[b] + 1, x)
def addst(self, a, x, q):
q(self.in_[a], self.out[a], x)
e = 10**18
id_ = 0
def op(s, t):
return min(s, t)
def mapping(f, a):
return a + f
def composition(f, g):
return f + g
# Main code
N, Q = map(int, input().split())
ans = N
edges = []
init_c = [-1] * N
hld = HLD(N)
for _ in range(N - 1):
a, b, c = map(int, input().split())
a -= 1
b -= 1
edges.append([a, b, c])
hld.edgeset(a, b )
hld.build()
A = [-1] * N
seg2 = DualSegmentTree(N, lambda x,y: x+ y, 0)
for i in range(N - 1):
if hld.dep[edges[i][0]] > hld.dep[edges[i][1]]:
edges[i][0], edges[i][1] = edges[i][1], edges[i][0]
A[hld.in_[edges[i][1]]] = edges[i][2]
init_c[edges[i][1]] = edges[i][2]
init_c[0] = float('inf')
A[hld.in_[0]] = float('inf')
seg = LazySegmentTree(A, float("inf"), op, id_, mapping, composition)
for i in range(N):
seg2.update(hld.in_[i], hld.in_[i]+1, hld.sz[i])
for _ in range(Q):
type_, *rest = map(int, input().split())
if type_ == 1:
v, x = rest
v -= 1
hld.addpath(0, v, -x, lambda a, b, x: seg.apply_range(a, b, x))
w = hld.nibutan(0, v, lambda a, b: seg.nibutan_query(a, b))
if w == -1:
continue
subtree_sz = seg2.get(hld.in_[w])
ans -= subtree_sz
hld.addpath(0, hld.par[w], -subtree_sz, lambda a, b, x: seg2.update(a, b, x))
w_apple = init_c[w] - seg.prod(hld.in_[w], hld.in_[w]+1)
hld.addpath(0, w, w_apple, lambda a, b, x: seg.apply_range(a, b, x))
if type_ == 2:
print(ans)