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