11615: 【原1615】Little Red Riding Hood
题目
题目描述
author: Spy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1615
Description
Amy住在一个树形的城市里，城里有n个编号为1~n的路口，某些路口间会有道路相连，显然，任何两个路口间存在唯一的最短路径。城市偶尔会下雨，下雨后路上会长蘑菇；Amy偶尔会去看望外婆，外婆喜欢吃蘑菇。
接下来给出一系列事件：
1、路口u、v间的道路上下了一场雨，每条路上新长出了w个蘑菇。
2、Amy要从路口u出发，去往路口v看望外婆，一路上她要采完所有的蘑菇带给外婆。
请你在每次看望外婆的时候告诉她今天有多少蘑菇。
Input Format
第一行有两个整数n,q ，分别代表路口的个数和事件的个数。
接下来 n-1 行给出路口之间的道路连接情况，每行是一对路口序号（u，v）
接下来 q 行，每行前三个 op,u,v。其中 op 代表事件的类型。若 op = 1，代表下了一场雨，下雨的路径区间为 [u,v]，第四个整数w代表每条路上新长的蘑菇个数；如果 op = 2，代表Amy采了一路蘑菇，被采蘑菇的区间为 [u,v]。
Output Format
对于每次拜访外婆，输出一行代表今天采到的蘑菇数。
Sample Input
5 3
1 2
1 3
2 4
3 5
1 4 5 1
2 4 3
2 4 5
Sample Output
3
1
Limits
- 初始道路上没有长蘑菇
- 对于50%的数据，城市是链状城市。
- 对于80%的数据，n,q < 10^3。
- 对于100%的数据，城市是树状城市，以1为根时的深度<100, n,q < 10^5，w<1000。
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！