Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!