"""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 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<>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] - hld.query(w, w, 0, lambda a, b: seg.prod(a, b), min) hld.addpath(0, w, w_apple, lambda a, b, x: seg.apply_range(a, b, x)) if type_ == 2: print(ans)