当前位置: 首页 > >

codeforces 1076E Vasya and a Tree 树上主席树

发布时间:

E. Vasya and a Tree


题意:给你一棵1为根节点的树,初始每个节点权值为0,有m次操作,每次操作 v d x,表示将以v为根的子树,深度不超过d的所有节点加上x。


思路:从深度为1的根节点开始遍历,到了深度为dep的v节点,若是该节点有操作 d x,那么以该节点为根的主席树就要在dep+d的点加上一个权值x,然后怎么计算该点的答案呢,该点的答案就是该点的主席树区间 [ dep, n ]和。


#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
ll sum[maxn*20],ans[maxn];
int ls[maxn*20],rs[maxn*20],cnt=0,n;
struct node
{
int d,x;
node(int a,int b)
{
d=a,x=b;
}
};
vectorq[maxn];
vectorG[maxn];
void up(int pre,int &o,int l,int r,int k,int v)
{
o=++cnt;
ls[o]=ls[pre],rs[o]=rs[pre];
sum[o]=sum[pre]+v;
if(l==r)return;
int m=(l+r)/2;
if(k<=m)up(ls[pre],ls[o],l,m,k,v);
else up(rs[o],rs[o],m+1,r,k,v);
}
ll qu(int o,int l,int r,int k)
{
if(l>=k||!sum[o])return sum[o];
int m=(l+r)/2;
ll res=qu(rs[o],m+1,r,k);
if(k<=m)res+=qu(ls[o],l,m,k);
return res;
}
void dfs(int u,int pre,int fa,int dep)
{
int rt=0;
for(int i=0;i {
int k=min(n,q[u][i].d+dep);
if(!rt)up(pre,rt,1,n,k,q[u][i].x);
else up(rt,rt,1,n,k,q[u][i].x);
}
if(!rt)rt=pre;
ans[u]=qu(rt,1,n,dep);
for(int i=0;i if(G[u][i]!=fa)
dfs(G[u][i],rt,u,dep+1);
}
int main()
{
int u,v,x,op;
scanf("%d",&n);
for(int i=1;i {
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
scanf("%d",&op);
while(op--)
{
scanf("%d%d%d",&u,&v,&x);
v=min(v,n);
q[u].push_back(node(v,x));
}
dfs(1,0,0,1);
for(int i=1;i printf("%I64d
",ans[n]);
}

?



友情链接: