一棵有N个节点的树，每个节点对应1个编号及1个权值，有2种不同的操作。
操作1：S x y z，表示如果编号为x的节点的权值 < y，则将节点x的权值加上z。(Single)
操作2：A x y z，表示如果编号为x的节点以及其所有子节点的权值平均值 < y，则将节点x及其所有子节点的权值加上z。(All)
给出树节点之间的关系，进行M次操作，问所有操作完成后，各个节点的权值为多少？
节点的编号为0 - N - 1，根节点的编号为0，并且初始情况下，根节点的权值也是0。
Input
第1行：2个数N, M，N为节点的数量，M为操作的数量(1 <= N, M <= 50000)。
第2 - N行：每行描述一个节点N[i]的信息，第2行对应编号为1的节点，第N行对应编号为N - 1的节点。具体内容为：每行2个数P[i], W[i]。P[i]为当前节点的父节点的编号，W[i]为当前节点的权值。(0 <= W[i] <= 10^5, P[i] < i)
第N + 1 - N + M行：每行表示一个操作，S x y z或A x y z，（0 <= y, z <= 10^5)。
Output
输出共N行，每行1个数W[i]，表示经过M次后，编号为0 - N - 1的节点的权值。
Input示例
4 3
0 10
0 10
1 2
S 0 1 1
A 0 20 1
S 3 2 1
Output示例
2
11
11
3 思路：
很简单的一道树链剖分+线段树，写起来麻烦点。。代码量有点大，一不小心就打错了。找半天。。 实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid ll m = (l + r) >> 1
const ll M = 7e5+;
struct node{
ll to,next;
}e[M];
ll n,m,cnt1,cnt,a[M];
ll sum[M<<],lazy[M<<],son[M],fa[M],head[M],siz[M],top[M],dep[M],tid[M],rk[M],mx[M];
void add(ll u,ll v){
e[++cnt1].to = v;e[cnt1].next = head[u];head[u] = cnt1;
e[++cnt1].to = u;e[cnt1].next = head[v];head[v] = cnt1;
} void dfs1(ll u,ll faz,ll deep){
dep[u] = deep;
fa[u] = faz;
siz[u] = ;
for(ll i = head[u];i;i=e[i].next){
ll v = e[i].to;
if(v != fa[u]){
dfs1(v,u,deep+);
siz[u] += siz[v];
if(son[u] == -||siz[v] > siz[son[u]])
son[u] = v;
}
}
} void dfs2(ll u,ll t){
top[u] = t;
mx[u] = cnt;
tid[u] = cnt;
rk[cnt] = u;
cnt++;
if(son[u] == -) return;
dfs2(son[u],t),mx[u] = max(mx[u],mx[son[u]]);
for(ll i = head[u];i;i = e[i].next){
ll v = e[i].to;
if(v != son[u]&&v != fa[u])
dfs2(v,v),mx[u]=max(mx[u],mx[v]);
}
} void scan_d ( ll& x , char c = , ll flag = ) {
while ( ( c = getchar () ) != '-' && ( c < '' || c > '' ) ) ;
if ( c == '-' ) flag = , x = ;
else x = c - '' ;
while ( ( c = getchar () ) >= '' && c <= '' ) x = x * + c - '' ;
if ( flag ) x = -x ;
} void pushup(ll rt){
sum[rt] = sum[rt<<] + sum[rt<<|];
} void build(ll l,ll r,ll rt){
if(l == r){
sum[rt] = a[rk[l]];
//cout<<"l: "<<l<<" sum: "<<sum[rt]<<" al: "<<rk[l]<<endl;
return ;
}
mid;
build(lson);
build(rson);
pushup(rt);
} void update(ll p,ll c,ll l,ll r,ll rt){
if(l == r){
sum[rt] += c;
return ;
}
mid;
if(p <= m) update(p,c,lson);
else update(p,c,rson);
pushup(rt);
} void pushdown(ll l,ll r,ll rt){
if(lazy[rt]){
mid;
lazy[rt<<]+=lazy[rt];
lazy[rt<<|]+=lazy[rt];
sum[rt<<]+=lazy[rt]*(m-l+);
sum[rt<<|]+=lazy[rt]*(r-m);
lazy[rt] = ;
}
} ll query(ll L,ll R,ll l,ll r,ll rt){
if(L <= l&&R >= r){
return sum[rt];
}
//cout<<l<<" "<<r<<endl;
pushdown(l,r,rt);
mid;
ll ret = ;
if(L <= m) ret += query(L,R,lson);
if(R > m) ret += query(L,R,rson);
return ret;
} void update1(ll L,ll R,ll c,ll l,ll r,ll rt){
if(l == r){
sum[rt]+=c;
return ;
}
if(L <= l&&R >= r){
sum[rt]+=c*(r-l+);
lazy[rt]+=c;
return ;
}
mid;
pushdown(l,r,rt);
if(L <= m) update1(L,R,c,lson);
if(R > m) update1(L,R,c,rson);
pushup(rt);
} ll query1(ll p,ll l,ll r,ll rt){
if(l == r) return sum[rt];
pushdown(l,r,rt);
mid;
if(p <= m) return query1(p,lson);
else return query1(p,rson);
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
ll u,w;
cin>>n>>m;
a[] = ;
memset(son,-,sizeof(son));
for(ll i = ;i < n;i ++){
cin>>u>>w;
add(u,i);a[i]=w;
}
dfs1(,-,); dfs2(,); build(,n-,);
char op;
ll x,y,z;
while(m--){
cin>>op>>x>>y>>z;
if(op == 'A'){
ll ans = query(tid[x],mx[x],,n-,);
double num = ans*1.0/(mx[x]-tid[x]+);
if(num < y) update1(tid[x],mx[x],z,,n-,);
}
else{
ll ans = query1(tid[x],,n-,);
if(ans < y) update(tid[x],z,,n-,);
}
}
for(ll i = ;i < n;i ++){
cout<<query1(tid[i],,n-,)<<endl;;
}
return ;
}