fork(5) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
10000
https://ideone.com/YvK3tN
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!