F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 4372. -- 烁烁的游戏

4372: 烁烁的游戏

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 1088  Solved: 405
[Submit][Status][Discuss]

Description

背景:烁烁很喜欢爬树,这吓坏了树上的皮皮鼠。
题意:
给定一颗n个节点的树,边权均为1,初始树上没有皮皮鼠。
烁烁他每次会跳到一个节点u,把周围与他距离不超过d的节点各吸引出w只皮皮鼠。皮皮鼠会被烁烁吸引,所以会一直待在节点上不动。
烁烁很好奇,在当前时刻,节点u有多少个他的好朋友---皮皮鼠。
大意:
给一颗n个节点的树,边权均为1,初始点权均为0,m次操作:
Q x:询问x的点权。
M x d w:将树上与节点x距离不超过d的节点的点权均加上w。

Input

第一行两个正整数:n,m
接下来的n-1行,每行三个正整数u,v,代表u,v之间有一条边。
接下来的m行,每行给出上述两种操作中的一种。

Output

对于每个Q操作,输出当前x节点的皮皮鼠数量。

Sample Input

7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2

Sample Output

2
3
6

HINT

数据范围:

n,m<=10^5,|w|<=10^4

注意:w不一定为正整数,因为烁烁可能把皮皮鼠吓傻了。

Source

[Submit][Status][Discuss]

HOME Back