1 条题解
-
0
#include<bits/stdc++.h> #define LL long long #define eb emplace_back using namespace std; const int N=1e6+10; vector<int>G[N]; LL v[N],a[N],d[N]; int dfn[N],siz[N],tsp,n,m,rt;; void dfs(int x,int xfa) { dfn[x]=++tsp;siz[x]=1; for(int y:G[x])if(y!=xfa) { dfs(y,x); siz[x]+=siz[y]; } } LL c1[N],c2[N]; void add(LL c[],int x,LL k){for(;x<=n;x+=x&-x)c[x]+=k;} LL sum(LL c[],int x){LL res=0;for(;x>=1;x-=x&-x)res+=c[x]; return res;} LL getsum(int x){ return sum(c1,x)*x-sum(c2,x); } int main() { scanf("%d%d%d",&n,&m,&rt); for(int i=1;i<=n;i++)scanf("%lld",&v[i]); for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),G[x].eb(y),G[y].eb(x); tsp=0;dfs(rt,0); a[0]=0;for(int i=1;i<=n;i++)a[dfn[i]]=v[i]; memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2)); for(int i=1;i<=n;i++) { d[i]=a[i]-a[i-1]; add(c1,i,d[i]), add(c2,i,d[i]*(i-1)); } for(int i=1;i<=m;++i) { int op;scanf("%d",&op); if(op==1)//1 x k,表示将结点 x 的子树上所有结点的权值增加 k { int p;LL k;scanf("%d%lld",&p,&k); int l=dfn[p],r=dfn[p]+siz[p]-1; add(c1,l,k); add(c1,r+1,-k); add(c2, l , k*(l-1) ); add(c2, r+1, -k*r ); } else//2 x,表示求结点 x 的子树上所有结点的权值之和 { int x;scanf("%d",&x); int l=dfn[x],r=dfn[x]+siz[x]-1; printf("%lld\n", getsum(r) - getsum(l-1) ); } } return 0; }
- 1
信息
- ID
- 118
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 196
- 已通过
- 20
- 上传者