daily pastebin goal
77%
SHARE
TWEET

Untitled

a guest Feb 24th, 2013 791 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top