http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1199
题意:
思路:
因为是一棵树,所以需要把它剖分一下再映射到线段树上,剖分的话只需要dfs一遍树即可,得到的dfs序就是每个结点在线段树中的位置,子树上的节点的编号都是连续的。
接下来的操作就是线段树的查询和更新了,这部分并不难。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=+; ll n, m, dfs_clock;
int w[maxn],son[maxn],dfn[maxn],num[maxn];
ll lazy[maxn<<]; vector<int> G[maxn]; struct node
{
int l, r;
ll sum;
}t[maxn<<]; void dfs(int u)
{
dfn[u]=++dfs_clock;
son[u]=;
for(int i=;i<G[u].size();i++)
{
int v=G[u][i];
dfs(v);
son[u]+=son[v];
}
} void PushUp(int o)
{
t[o].sum=t[o<<].sum+t[o<<|].sum;
} void PushDown(int o)
{
if(lazy[o])
{
lazy[o<<]+=lazy[o];
lazy[o<<|]+=lazy[o];
int m=t[o].r-t[o].l+;
t[o<<].sum+=lazy[o]*(m-(m>>));
t[o<<|].sum+=lazy[o]*(m>>);
lazy[o]=;
}
} void build(int l ,int r, int o)
{
lazy[o]=;
t[o].l=l;
t[o].r=r;
t[o].sum=;
if(l==r)
{
t[o].sum=num[l];
return;
}
int mid=(l+r)>>;
build(l,mid,o<<);
build(mid+,r,o<<|);
PushUp(o);
} void update(int ql, int qr, int l, int r, ll z, int o)
{
if(ql<=l && qr>=r)
{
t[o].sum+=(r-l+)*z;
lazy[o]+=z;
return;
}
PushDown(o);
int mid=(l+r)>>;
if(ql<=mid) update(ql,qr,l,mid,z,o<<);
if(qr>mid) update(ql,qr,mid+,r,z,o<<|);
PushUp(o);
} ll query(int ql, int qr, int l, int r, int o)
{
if(ql<=l && qr>=r) return t[o].sum;
PushDown(o);
int mid=(l+r)>>;
ll ans=;
if(ql<=mid) ans+=query(ql,qr,l,mid,o<<);
if(qr>mid) ans+=query(ql,qr,mid+,r,o<<|);
return ans;
} int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) G[i].clear();
for(int i=;i<n;i++)
{
int p; scanf("%d%d",&p,&w[i]);
G[p].push_back(i);
}
w[]=;
dfs_clock=;
dfs();
for(int i=;i<n;i++) num[dfn[i]]=w[i];
build(,n,);
char op[]; ll x, y, z;
memset(lazy,,sizeof(lazy));
while(m--)
{
scanf("%s%lld%lld%lld",op,&x,&y,&z);
if(op[]=='S')
{
if(query(dfn[x],dfn[x],,n,)<y) update(dfn[x],dfn[x],,n,z,);
}
else
{
if(query(dfn[x],dfn[x]+son[x]-,,n,)<son[x]*y) update(dfn[x],dfn[x]+son[x]-,,n,z,);
}
}
for(int i=;i<n;i++) printf("%lld\n",query(dfn[i],dfn[i],,n,));
return ;
}