結果
| 問題 |
No.2439 Fragile Apple Tree
|
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2023-08-15 02:19:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,245 bytes |
| コンパイル時間 | 436 ms |
| コンパイル使用メモリ | 81,792 KB |
| 実行使用メモリ | 644,644 KB |
| 最終ジャッジ日時 | 2024-11-23 05:23:52 |
| 合計ジャッジ時間 | 318,868 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 TLE * 26 MLE * 2 |
ソースコード
class LazySegTree:
def __init__(self, n):
self.sz = 1
while self.sz < n:
self.sz *= 2
self.node = [float('inf')] * (2 * self.sz - 1)
self.lazy = [0] * (2 * self.sz - 1)
self.lazyFlag = [False] * (2 * self.sz - 1)
def eval(self, k, l, r):
if self.lazyFlag[k]:
self.node[k] += self.lazy[k]
if r - l > 1:
self.lazy[2 * k + 1] += self.lazy[k]
self.lazy[2 * k + 2] += self.lazy[k]
self.lazyFlag[2 * k + 1] = self.lazyFlag[2 * k + 2] = True
self.lazyFlag[k] = False
self.lazy[k] = 0
def update(self, a, b, x, k=0, l=0, r=-1):
if r < 0:
r = self.sz
self.eval(k, l, r)
if b <= l or r <= a:
return
if a <= l and r <= b:
self.lazy[k] = x
self.lazyFlag[k] = True
self.eval(k, l, r)
else:
self.update(a, b, x, 2 * k + 1, l, (l + r) // 2)
self.update(a, b, x, 2 * k + 2, (l + r) // 2, r)
self.node[k] = min(self.node[2 * k + 1], self.node[2 * k + 2])
def update_single(self, a, x):
self.update(a, a + 1, x)
def query(self, a, b, k=0, l=0, r=-1):
if r < 0:
r = self.sz
self.eval(k, l, r)
if b <= l or r <= a:
return float('inf')
if a <= l and r <= b:
return self.node[k]
vl = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
vr = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
return min(vl, vr)
def nibutan_query(self, a, b):
res = self.nibutan(a, b)
return -1 if res == a - 1 else res
def nibutan(self, a, b, k=0, l=0, r=-1):
if r < 0:
r = self.sz
self.eval(k, l, r)
if self.node[k] > 0 or r <= a or b <= l:
return a - 1
elif r - l == 1:
return k - (self.sz - 1)
else:
vr = self.nibutan(a, b, 2 * k + 2, (l + r) // 2, r)
if vr != a - 1:
return vr
else:
return self.nibutan(a, b, 2 * k + 1, l, (l + r) // 2)
def init(self):
for i in range(self.sz-2, -1, -1):
self.node[i] = min(self.node[i*2+1], self.node[i*2+2])
class SegTree:
def __init__(self, n):
self.sz = 1
while self.sz < n:
self.sz *= 2
self.dat = [0] * (2 * self.sz - 1)
def update(self, a, b, x, k=0, l=0, r=-1):
if r < 0:
r = self.sz
if r <= a or b <= l:
return
if a <= l and r <= b:
self.dat[k] += x
return
self.update(a, b, x, 2 * k + 1, l, (l + r) // 2)
self.update(a, b, x, 2 * k + 2, (l + r) // 2, r)
def query(self, a):
a += self.sz - 1
res = 0
while a > 0:
res += self.dat[a]
a = (a - 1) // 2
return res
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]
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)
# 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': a, 'b': b , 'c': c})
hld.edgeset(a, b )
hld.build()
seg = LazySegTree(300010)
seg2 = SegTree(300010)
for i in range(N - 1):
if hld.dep[edges[i]['a']] > hld.dep[edges[i]['b']]:
edges[i]['a'], edges[i]['b'] = edges[i]['b'], edges[i]['a']
seg.node[hld.in_[edges[i]['b']] + seg.sz - 1] = edges[i]['c']
init_c[edges[i]["b"]] = edges[i]["c"];
init_c[0] = float('inf')
seg.node[hld.in_[0] + seg.sz - 1] = float('inf')
seg.init()
p = []
for i in range(N):
p.append(seg.query(i, i+1))
for i in range(N):
seg2.dat[hld.in_[i] + seg2.sz - 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.update(a, b, x))
w = hld.nibutan(0, v, lambda a, b: seg.nibutan_query(a, b))
if w == -1:
continue
subtree_sz = seg2.query(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] - hld.query(w, w, 0, lambda a, b: seg.query(a, b), min)
hld.addpath(0, w, w_apple, lambda a, b, x: seg.update(a, b, x))
if type_ == 2:
print(ans)