题目描述

给定一棵 $N$ 个节点的树，每条边初始边权为 $0$，现在有两种操作：

• 1 u v c，表示把 $u$ 到 $v$ 路径上所有边的边权改为 $c$。

• 2 u v c，表示把 $u$ 到 $v$ 路径上所有边的边权加上 $c$。如果 $u$ 到 $v$ 的路径上某条边的边权加上 $c$ 后小于 $0$，那么将这条边的边权更改为 $0$。

每次操作后，你需要统计出树中边权为 $0$ 的边有多少条。

输入格式

第一行两个整数 $n,m$，分别表示表示节点个数与操作次数。

接下来 $n-1$ 行每行两个整数 $x,y$，表示 $x,y$ 之间有一条边。

接下来 $m$ 行，每行表示一个操作。

输出格式

输出共 $m$ 行，每行一个整数，表示边权为 $0$ 的边的个数。

5 4
1 2
1 3
2 4
2 5
1 4 5 1
2 5 3 1
2 5 1 -2
1 4 3 0

2
0
1
3

提示

对于 $100\%$ 的数据，$1\le n,m\le 10^5$。

题目来源

没有写明来源