Given a rooted tree ( the root is node 11 ) of NN nodes. Initially, each node has zero point.
Then, you need to handle QQ operations. There're two types:
1\ L\ X1 L X: Increase points by XX of all nodes whose depth equals LL ( the depth of the root is zero ). (x \leq 10^8)(x≤108)
2\ X2 X: Output sum of all points in the subtree whose root is XX.
Input
Just one case.
The first lines contain two integer, N,QN,Q. (N \leq 10^5, Q \leq 10^5)(N≤105,Q≤105).
The next n-1n−1 lines: Each line has two integer aa,bb, means that node aa is the father of node bb. It's guaranteed that the input data forms a rooted tree and node 11 is the root of it.
The next QQ lines are queries.
Output
For each query 22, you should output a number means answer.
样例输入
3 3 1 2 2 3 1 1 1 2 1 2 3
样例输出
1 0
SOLUTION:
第一次写分块这种的暴力的方法qwq
发现本题 查询子树和 与 修改相同深度的点的val时相互矛盾的
那就考虑怎么暴力吧
即,如果修改的那个层数的节点小于某个T,那么就直接用树状数组+DFS序维护子树和,暴力单点更新。
如果 大于> ,那么就用懒惰标记的思想,先把加了多少 记录下来,等查询的时候再暴力查询该子树,深度为某个值的节点个数,然后乘以该懒惰标记即可。那么这个T多大呢?明显是sqrt(N)。
那么查询某子树,深度为某个值的节点个数怎么做呢?先把节点按照dfs序编号,然后记录某层有哪些节点,最后二分查询即可。
CODE:
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; typedef long long ll; vector<int>G[maxn],dep[maxn],large; int st[maxn],ed[maxn],tim,n; ll tree[maxn],num[maxn]; void add(int pos,ll v) { for(;pos<=n;pos+=pos&-pos) tree[pos]+=v; } ll query(int pos) { ll ans=0; for(;pos;pos-=pos&-pos) ans+=tree[pos]; return ans; } void dfs(int u,int fa,int depth) //时间戳 { st[u]=++tim; dep[depth].push_back(tim); int sz=G[u].size(); for(int i=0;i<sz;i++) if(G[u][i]!=fa) dfs(G[u][i],u,depth+1); ed[u]=tim; } int main() { int q; scanf("%d%d",&n,&q); for(int i=0;i<n-1;i++) { int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1,0,0); int block=ceil(sqrt(n)); for(int i=0;i<n;i++) if(dep[i].size()>block) large.push_back(i); while(q--) { int nood; scanf("%d",&nood); if(nood==1) { int depth; ll v; scanf("%d%lld",&depth,&v); if(dep[depth].size()>block) num[depth]+=v; else { for(int i=0;i<dep[depth].size();i++) add(dep[depth][i],v); } } else { int x; scanf("%d",&x); ll ans=query(ed[x])-query(st[x]-1); for(int i=0;i<large.size();i++) ans+=(upper_bound(dep[large[i]].begin(),dep[large[i]].end(),ed[x])-lower_bound(dep[large[i]].begin(),dep[large[i]].end(),st[x]))*num[large[i]]; printf("%lld\n",ans); } } }