#BZOJ4353. Play with tree
-
ID: 2957
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Play with tree
No submission language available for this problem.
题目描述
给你一棵包含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