给一棵有根树,这棵树由编号为1~N 的 N个结点组成。根结点的编号为R。每个结点都有一个权值,结点 的权值为 。 接下来有 M组操作,操作分为两类:
1 a x,表示将结点 的子树上所有结点的权值增加 ;
2 a,表示求结点 的子树上所有结点的权值之和。
第一行有三个整数 N,M和R。
第二行有 N个整数,第 i个整数表示 vi。
在接下来的 N-1行中,每行两个整数,表示一条边。
在接下来的 M行中,每行一组操作。
对于每组 2 a操作,输出一个整数,表示「以结点 a为根的子树」上所有结点的权值之和。
用到了dfs序,两个数组 st[ ] ,en[ ] 储存每个点遍历的出入时间,通过时间可算出子树节点。
通过 mp[ ] 数组,找到结点与树的对应(映射)
用线段树的区间修改和区间查询,并结合 st[ ] , en[ ] 数组,找到所用的区间。
代码↓
#include
using namespace std;
const int N = 1e6 + 5;
vector q[N];
int st[N],en[N],tmp=0;
int n,m,r,b[N];
long long sum[N<<2],lazy[N<<2];
int mp[N];
void dfs(int u, int fa)
{
st[u]=++tmp;
mp[tmp] = u;
for(auto v:q[u])
{
if(v==fa) continue;
dfs(v,u);
}
en[u]=tmp;
}
int a[1005],c[1005];
void pushup(int i)
{
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void up(int i,long long len,long long v)
{
sum[i]+=len * v;
lazy[i]+=v;
}
void pushdown(int i,int l,int r)
{
int mid=(l+r)/2;
if(lazy[i])
{
up(i<<1,mid-l+1,lazy[i]);
up(i<<1|1,r-mid,lazy[i]);
lazy[i] = 0;
}
}
void build(int i,int l,int r)
{
if(l==r) {
sum[i] = b[mp[l]];
return ;
}
int mid=(l+r)/2;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
}
//区间修改
void zeng(int i,int ql,int qr,int l,int r,int v)
{
if(ql=r)
{
up(i,r-l+1,v);
return ;
}
int mid=(l+r)/2;
pushdown(i,l,r);
if(ql<=mid)
zeng(i<mid)
zeng(i<<1|1,ql,qr,mid+1,r,v);
pushup(i);
}
//区间查询
long long he(int i,int ql,int qr,int l,int r)
{
if(ql=r)
{
return sum[i];
}
int mid=(l+r)/2;
pushdown(i,l,r);
long long ans = 0;
if(ql<=mid)
ans+=he(i<mid)
ans+=he(i<>n>>m>>r;
for(int i=1;i>b[i];
}
int x,y;
for(int i=1;i>x>>y;
q[x].push_back(y);
q[y].push_back(x);
}
dfs(r,0);
// dfs序
build(1, 1, n);
int f;
while(m--)
{
cin>>f;
if(f==1)
{
cin>>x>>y;
// st[x], en[x]可找到子树的区间
zeng(1, st[x], en[x], 1, n, y);
}
else
{
cin>>x;
cout<<he(1,st[x],en[x],1,n)<<endl;
}
}
return 0;
}
师子墨么么么么么么
原创文章 1获赞 1访问量 43
关注
私信
展开阅读全文