fork(4) download
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define mp make_pair
  4. using namespace std;
  5. inline int scan(){
  6. char c = getchar();
  7. int x = 0;
  8. while(c<'0'||c>'9'){
  9. c=getchar();
  10. }
  11. while(c>='0'&&c<='9'){
  12. x=(x<<1)+(x<<3)+c-'0';
  13. c=getchar();
  14. }
  15. return x;
  16. }
  17. const int N = 100001;
  18. const int SQN = 350;
  19. int freq[SQN][N]={0};
  20. long long val[SQN]={0};
  21. int start[SQN];
  22. int finish[SQN];
  23. int n,sqn,m;
  24. int timer=0;
  25. int treestart[N];
  26. int treeend[N];
  27. int rev[N];
  28. list<int> v[N];
  29. int level[N]={0};
  30. int lookup[N];
  31. long long sum[N]={0};
  32. void dfs(int node,int parent){
  33. level[node]=level[parent]+1;
  34. treestart[node]=++timer;
  35. rev[timer]=node;
  36. for(list<int>::iterator it = v[node].begin();it!=v[node].end();++it){
  37. if(*it!=parent)
  38. dfs(*it,node);
  39. }
  40. treeend[node]=timer;
  41. }
  42. int main(){
  43. n=scan(),m=scan();
  44. for(int i=1;i<n;++i){
  45. int a=scan(),b=scan();
  46. v[a].pb(b);
  47. v[b].pb(a);
  48. }
  49. dfs(1,0);
  50. int sqn = sqrt(n);
  51. int cur=1;
  52. for(int i=1;i<=n;){
  53. int j=i;
  54. start[cur]=i;
  55. while(j<i+sqn&&j<=n){
  56. freq[cur][level[rev[j]]]++;
  57. j++;
  58. lookup[j-1]=cur;
  59. }
  60. i=j;
  61. finish[cur]=j-1;
  62. ++cur;
  63. }
  64. while(m--){
  65. int type=scan();
  66. if(type==1){
  67. int levl = scan();
  68. long long vall = scan();
  69. for(int i=1;i<cur;++i){
  70. val[i]+=1LL*freq[i][levl+1]*vall;
  71. }
  72. sum[levl+1]+=vall;
  73. }
  74. else{
  75. int node = scan();
  76. int x=lookup[treestart[node]];
  77. int y=lookup[treeend[node]];
  78. long long res=0;
  79. for(int i=x;i<=y;++i){
  80. if(start[i]>=treestart[node]&&finish[i]<=treeend[node]){
  81. res+=val[i];
  82. }
  83. else if(start[i]<treestart[node]){
  84. for(int j=treestart[node];j<=min(treeend[node],finish[i]);++j){
  85. res+=sum[level[rev[j]]];
  86. }
  87. }
  88. else{
  89. for(int j= max(start[i],treestart[node]);j<=treeend[node];++j){
  90. res+=sum[level[rev[j]]];
  91. }
  92. }
  93. }
  94. printf("%lld\n",res);
  95. }
  96. }
  97. }
Success #stdin #stdout 0s 143552KB
stdin
10 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 1 10000
2 1
stdout
10000