Play with tree

时间限制:20s      空间限制:256MB

题目描述

给你一棵包含N个节点的树,设每条边一开始的边权为0,现在有两种操作:
1)给出参数U,V,C,表示把U与V之间的路径上的边权变成C(保证C≥0)
2)给出参数U,V,C,表示把U与V之间的路径上的边权加上C。但是如果U至V之间路径某条边的边权加上C小于0,那么C=这条边的边权的相反数。
你需要统计出每次一操作过后树中边权为0的边有多少条。


输入格式

第一行两个整数N,M,分别表示表示节点个数与操作数。
接下来N-1行每行两个整数X,Y表示X,Y之间有一条边。
接下来M行每行4个整数P,U,V,C,P表示操作类型,U,V,C的意义见题目描述。


输出格式

输出文件包括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

提示

N, M≤100,000


题目来源

没有写明来源

Menuappsclose