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)