3768: Charles的树
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:13
解决:2
题目描述
Charles有一棵n个节点的树,节点的编号为0~n-1,每个节点有相应的权值,根节点权值为0,现在有以下两种操作:
S x y z,表示如果编号为x的节点的点权小于y,则将节点x的权值加z
A x y z,表示如果编号为x的节点及其子树上的所有节点的权值平均值小于y,则将节点x及其子树上的所有节点的权值加z
(0<=x<n,0<y,z<100000)
S x y z,表示如果编号为x的节点的点权小于y,则将节点x的权值加z
A x y z,表示如果编号为x的节点及其子树上的所有节点的权值平均值小于y,则将节点x及其子树上的所有节点的权值加z
(0<=x<n,0<y,z<100000)
输入
第一行两个数n,m(1<=n,m<=50000),n为节点数,m为操作的次数
以下n-1行(即第2~n行),有两个数x和y(0<=x<n,0<y<100000)。x为当前节点父节点的编号,y为当前节点的权值。第2行对应编号为1的节点,第n行对应编号为n-1的节点。
以下m行,代表m次操作。
以下n-1行(即第2~n行),有两个数x和y(0<=x<n,0<y<100000)。x为当前节点父节点的编号,y为当前节点的权值。第2行对应编号为1的节点,第n行对应编号为n-1的节点。
以下m行,代表m次操作。
输出
m次操作后所有节点的权值。
样例输入 复制
4 3
0 10
0 10
1 2
S 0 1 1
A 0 20 1
S 3 2 1
样例输出 复制
2
11
11
3