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]; int n,v[N]; int tsp,dfn[N],siz[N]; 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 c[N]; void add(int x,LL k){for(;x<=n;x+=x&-x)c[x]+=k;} LL sum(int x){LL res=0;for(;x>=1;x-=x&-x)res+=c[x]; return res;} int main() { int m,rt;scanf("%d%d%d",&n,&m,&rt); for(int i=1;i<=n;i++)scanf("%d",&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); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++)add(dfn[i],v[i]); for(int i=1;i<=m;++i) { int op;scanf("%d",&op); if(op==1)//1 x k:表示将结点 x 的权值增加 k; { int x;LL k;scanf("%d%lld",&x,&k); add(dfn[x],k); } else//2 x : 表示求结点 x 的子树上所有结点的权值之和。 { int x;scanf("%d",&x); int l=dfn[x],r=dfn[x]+siz[x]-1; printf("%lld\n", sum(r)-sum(l-1) ); } } return 0; }
- 1
信息
- ID
- 110
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 125
- 已通过
- 37
- 上传者