Guest User

Untitled

a guest
Feb 24th, 2013
1,011
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <string.h>
  4. #include <cstdlib>
  5. #include <set>
  6. #include <map>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <sstream>
  11. #include <memory.h>
  12. #include <stdio.h>
  13. #include <ctime>
  14. #include <cmath>
  15.  
  16.  
  17. using namespace std;
  18.  
  19.  
  20. char ch_ch_ch[1<<20];
  21. inline int gi() {int a; scanf("%d",&a); return a;}
  22. inline string gs() {scanf("%s",ch_ch_ch); return string(ch_ch_ch);}
  23. inline string gl() {gets(ch_ch_ch); return string(ch_ch_ch);}
  24. const int inf = 2000000000;
  25.  
  26. #define LL long long
  27. #define U unsigned
  28. #define pnt pair<int,int>
  29. #define FOR(i,a,b) for (int i=(a); i<(b); ++i)
  30. #define MEMS(a,b) memset((a),(b),sizeof(a))
  31. #define MAX(a,b) ((a)>(b)?(a):(b))
  32. #define MIN(a,b) ((a)<(b)?(a):(b))
  33. #define ABS(a) (((a)>=(0))?(a):(-(a)))
  34. #define mp make_pair
  35. #define pb push_back
  36. #define ALL(a) a.begin(),a.end()
  37. #define FI(i,b) FOR(i,0,b)
  38. #define V(t) vector < t >
  39. #define sz size()
  40.  
  41. vector<vector<int> > g;
  42. int inTree[100100];
  43. int depth[100100];
  44. vector<vector<int> > t;
  45. void dfs(int v, int d, int num, int p)
  46. {
  47.     inTree[v]=num;
  48.     depth[v]=d;
  49.     t[num].push_back(0);
  50.     FOR(i,0,g[v].size())
  51.     {
  52.         int to=g[v][i];
  53.         if (to==p)
  54.             continue;
  55.         dfs(g[v][i],d+1,num,v);
  56.     }
  57. }
  58. void add(int p, int v, int num)
  59. {
  60.     for (int i=p; i<t[num].size(); i+=(i&(-i)))
  61.         t[num][i]+=v;
  62. }
  63. int find(int p, int num)
  64. {
  65.     int res=0;
  66.     for (int i=p; i>0; i-=(i&(-i)))
  67.         res+=t[num][i];
  68.     return res;
  69. }
  70. int main()
  71. {
  72. #ifdef Fcdkbear
  73.     double beg=clock();
  74.     freopen("in.txt","r",stdin);
  75. #endif
  76.  
  77.     int n,q;
  78.     scanf("%d%d",&n,&q);
  79.     g.resize(n);
  80.     FOR(i,0,n-1)
  81.     {
  82.         int v1,v2;
  83.         scanf("%d%d",&v1,&v2);
  84.         v1--;
  85.         v2--;
  86.         g[v1].push_back(v2);
  87.         g[v2].push_back(v1);
  88.     }
  89.     t.resize(g[0].size()+1);
  90.     int inRoot=0;
  91.     FOR(i,0,g[0].size())
  92.     {
  93.         t[i].push_back(0);
  94.         dfs(g[0][i],1,i,0);
  95.     }
  96.     t[t.size()-1].resize(n+10);
  97.     FOR(i,0,q)
  98.     {
  99.         int ty;
  100.         scanf("%d",&ty);
  101.         if (ty==0)
  102.         {
  103.             int v,val,dist;
  104.             scanf("%d%d%d",&v,&val,&dist);
  105.             v--;
  106.             if (v==0)
  107.             {
  108.                 inRoot+=val;
  109.                 add(1,val,t.size()-1);
  110.                 add(dist+1,-val,t.size()-1);
  111.             }
  112.             else
  113.             {
  114.                 if (dist>=depth[v])
  115.                 {
  116.                     int left=dist-depth[v];
  117.                     inRoot+=val;
  118.                     add(1,val,t.size()-1);
  119.                     add(left+1,-val,t.size()-1);
  120.                     add(left+1,val,inTree[v]);
  121.                     add(depth[v]+dist+1,-val,inTree[v]);
  122.                 }
  123.                 else
  124.                 {
  125.                     add(depth[v]-dist,val,inTree[v]);
  126.                     add(depth[v]+dist+1,-val,inTree[v]);
  127.                 }
  128.             }
  129.         }
  130.         else
  131.         {
  132.             int v;
  133.             scanf("%d",&v);
  134.             v--;
  135.             if (v==0)
  136.                 printf("%d\n",inRoot);
  137.             else
  138.             {
  139.                 int res=find(depth[v],inTree[v])+find(depth[v],t.size()-1);
  140.                 printf("%d\n",res);
  141.             }
  142.         }
  143.     }
  144. #ifdef Fcdkbear
  145.     double end=clock();
  146.     fprintf(stderr,"*** Time = %.3lf ***\n",(end-beg)/CLOCKS_PER_SEC);
  147. #endif
  148.     return 0;
  149. }
RAW Paste Data