API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
69
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.63 KB | None | 0 0
raw download clone embed print report
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <sstream>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <cmath>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <list>
  11. #include <iostream>
  12. #include <fstream>
  13. #include <numeric>
  14. #include <string>
  15. #include <vector>
  16. #include <cstring>
  17. #include <map>
  18. #include <iterator>
  19. #include <deque>
  20. #include <climits>
  21. #include <complex>
  22. #include <bitset>
  23.  
  24. using namespace std;
  25.  
  26. #define LL                          long long
  27. #define ULL                         unsigned long long
  28.  
  29. // I/O
  30. #define I(X)                        scanf("%d",     &(X))
  31. #define II(X, Y)                    scanf("%d%d",   &(X), &(Y))
  32. #define III(X, Y, Z)                scanf("%d%d%d", &(X), &(Y), &(Z))
  33.  
  34. #define IL(X)                       scanf("%lld", &X)
  35. #define IIL(X,Y )                   scanf("%lld%lld", &X,&Y)
  36. #define IIIL(X,Y,Z)                 scanf("%lld%lld%lld", &X,&Y,&Z)
  37.  
  38. #define ID(x)                       scanf("%lf",&x)
  39. #define IID(x,y)                    scanf("%lf%lf",&x,&y)
  40. #define IIID(x,y,z)                 scanf("%lf%lf%lf",&x,&y,&z)
  41.  
  42. #define DI(X)         int X;        I(X);
  43. #define DII(X, Y)     int X, Y;     II(X,Y)
  44. #define DIII(X, Y, Z) int X, Y, Z;  III(X,Y,Z);
  45.  
  46. #define DIL(X)        LL X;         IL(X)
  47. #define DIIL(X,Y)     LL X,Y;       IIL(X,Y)
  48. #define DIIIL(X,Y,Z)  LL X,Y,Z;     IIIL(X,Y,Z)
  49.  
  50.  
  51. #define SS(s)                       scanf("%s",s)
  52. #define S                           scanf
  53. #define P                           printf
  54.  
  55. #define PI(x)                       printf("%d\n",      x)
  56. #define PII(x,y)                    printf("%d %d\n",   x,y)
  57. #define PIII(x,y,z)                 printf("%d %d %d\n",x,y,z)
  58.  
  59. #define PIL(x)                      printf("%lld\n",          x)
  60. #define PIIL(x,y)                   printf("%lld %lld\n",     x,y)
  61. #define PIIIL(x,y,z)                printf("%lld %lld %lld\n",x,y,z)
  62.  
  63. // LOOP
  64. #define repv(i,a)                   for(int i=0;i<(int)a.size();i++)
  65. #define revv(i,a)                   for(int i=((int)a.size())-1;i>=0;i--)
  66. #define rep(i,a,b)                  for(int i=a;i<=b;i++)
  67. #define rev(i,a,b)                  for(int i=a;i>=b;i--)
  68.  
  69. #define FS(x)                       for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
  70. #define PR(x)                       for(typeof (x.begin()) it = x.begin(); it != x.end (); it++) {  cout << *it << " "; } cout << endl;
  71.  
  72. // array initialization
  73. #define MEM(a,val)                  memset(a,val,sizeof(a));
  74. #define SET(a)                      memset(a,-1,sizeof a)
  75. #define CLR(a)                      memset(a,0,sizeof a)
  76.  
  77. // min-max
  78. #define Max(a,b)                    (a>b?a:b)
  79. #define _Max(a,b,c)                 Max(a,Max(b,c))
  80. #define Min(a,b)                    (a<b?a:b)
  81. #define _Min(a,b,c)                 Min(a,Min(b,c))
  82. #define MAX(a)                      (*max_element(all(a)))
  83. #define MIN(a)                      (*min_element(all(a)))
  84.  
  85. #define FastMax(x,y)                ((((y-x)>>(32-1))&(x^y))^y)
  86. #define FastMin(x,y)                ((((y-x)>>(32-1))&(x^y))^x)
  87.  
  88. #define SQR(n)          (n*n)
  89.  
  90. #define all(a)          a.begin(),a.end()
  91. #define pb              push_back
  92. #define NL              puts("");
  93. #define pline           cout << "_________________________" << endl;
  94. // pair
  95. #define XX              first
  96. #define YY              second
  97. // binary search
  98. #define LB(a,x)         (lower_bound(all(a),x)-a.begin())
  99. #define UB(a,x)         (upper_bound(all(a),x)-a.begin())
  100. // IO
  101. #define READ            freopen("C:\\Users\\backbencher\\Desktop\\input.txt","r",stdin)
  102. #define WRITE           freopen("C:\\Users\\backbencher\\Desktop\\output.txt","w",stdout)
  103.  
  104. #define _cin            ios_base::sync_with_stdio(0); cin.tie(0);
  105.  
  106. #define SI(X)           X=in<int>()
  107. #define SII(X,Y)        X=in<int>(),Y=in<int>()
  108. #define SIII(X,Y,Z)     X=in<int>(),Y=in<int>(),Z=in<int>()
  109.  
  110. #define SL(X)           X=in<LL>()
  111. #define SLL(X,Y)        X=in<LL>(),Y=in<LL>()
  112. #define SLLL(X,Y,Z)     X=in<LL>(),Y=in<LL>(),Z=in<LL>()
  113.  
  114. #define VI              vector< int >
  115. #define VII             vector< VI >
  116. #define VLL             vector< LL >
  117. #define PPI             pair< int , int >
  118. #define PPL             pair< LL , LL >
  119. #define VPI             vector< PPI >
  120.  
  121. #define SEG             int mid=(s+e)>>1,l=(idx<<1),r=(l|1);
  122. #define in(x,l,r)       ( l<=x && x<=r )
  123.  
  124. // Bit-op
  125. #define countbit(x)     __builtin_popcount(x)
  126. template< class T, class X > inline bool checkbit(T a, X pos) { T t=1;return ((a&(t<<pos))>0);  }
  127. template< class T, class X > inline T      setbit(T a, X pos) { T t=1;return (a|(t<<pos));      }
  128. template< class T, class X > inline T    resetbit(T a, X pos) { T t=1;return (a&(~(t<<pos)));   }
  129. template< class T, class X > inline T   togglebit(T a, X pos) { T t=1;return (a^(t<<pos));      }
  130. // mathematics
  131. template<typename T> T POW(T base,T power)              { T ret=1; while(power)  { if(power & 1) ret=(ret*base); base=(base*base);  power>>=1; }return ret; }
  132. template<typename T> T PPOW(T B,T P)                    { if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return SQR(POW(B,P/2));}
  133. template<typename T> T Bigmod(T base,T power,T mod)     { T ret=1; while(power)  { if(power & 1) ret=(ret*base)%mod; base=(base*base)%mod;  power>>=1; }return ret; }
  134. template<typename T> T ModInverse(T number,T mod)       { return Bigmod(number,mod-2,mod); }
  135. template<typename T> T GCD(T a,T b)                     { if(a<0)return GCD(-a,b);if(b<0)return GCD(a,-b);return (b==0)?a:GCD(b,a%b);}
  136. template<typename T> T LCM(T a,T b)                     { if(a<0)return LCM(-a,b);if(b<0)return LCM(a,-b);return a*(b/GCD(a,b));}
  137. template<typename T> T EUCLIDE(T a,T b,T &x,T &y)       { if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;}   if(b<0){T d=euclide(a,-b,x,y);y=-y;return d;}   if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,x,y);T t=x;x=y;y=t-(a/b)*y;return d;}}
  138. template<typename T> T ABS(T a)                         { if(a<0)return -a;else return a;}
  139. // geometry
  140. template<typename T> double PDIS(T x1,T y1,T x2, T y2)   { return sqrt( (double)( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) );}
  141. template<typename T> T ANGLE(T x1,T y1,T x2, T y2)      { return atan( double(y1-y2) / double(x1-x2));}
  142. template<typename T> LL isLeft(T a,T b,T c)             { return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y); }
  143. // Degree and Radian
  144. //double DEG(double x) { return (180.0*x)/(pi);}
  145. //double RAD(double x) { return (x*(double)pi)/(180.0);}
  146.  
  147. // debug
  148. void P_ARR(int *ar,int a,int b) {  if(a>b) swap(a,b); if(a<=b) cout << ar[a]; for(int i=a+1;i<=b;i++) cout << " "<<ar[i];  cout << endl; }
  149. template<typename T> T In(){ char ch; T n = 0; bool ng = false; while (1) { ch = getchar(); if (ch == '-') { ng = true; ch = getchar(); break;} if (ch>='0' && ch<='9') break; }    while (1) { n = n*10 + (ch - '0'); ch = getchar(); if (ch<'0' || ch>'9')   break;    }  return (ng?-n:n);  }
  150.  
  151. //int month[]={31,28,31,30,31,30,31,31,30,31,30,31};                                    /// month
  152. int dir[5][2] = { {0,0},{1,0},{0,1},{-1,0},{0,-1} };                                  /// 4 Direction
  153. //int dir[9][2] = { {0,0},{1,0},{0,1},{-1,0},{0,-1},{-1,1},{-1,-1},{1,-1},{1,1}};       /// 8 direction
  154. //int dir[9][2] = { {0,0},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1} };    /// Knight Direction
  155. //int dir[8][2] = { {0,0},{2,0},{1,1},{-1,1} ,{-2,0} , {-1,-1} ,{1,-1} };               /// Hexagonal Direction
  156. // dir[][0] = x value, dir[][1] = y value
  157.  
  158. /// ======================================================================================================
  159.  
  160. #define  debug  0
  161. #define  DD     if(debug)
  162.  
  163. #define eps     (1e-9)
  164. #define pi      (2.0*acos(0.0)) //#define PI acos(-1.0)
  165. ///             0123456789
  166. #define  MX     300007
  167. #define  MOD    1000000007
  168. #define  inf    100000000
  169.  
  170.  
  171. vector<int>adj[MX];
  172.  
  173. int subtree[MX];
  174. int removed[MX];
  175. int par[MX];
  176. int level[MX];
  177. int res[MX];
  178. int tot;
  179. int dis[19][MX];
  180.  
  181. void dfs(int u,int papa)
  182. {
  183.     tot++;
  184.     subtree[u] = 1;
  185.     repv(i,adj[u]){
  186.         int v = adj[u][i];
  187.         if( v==papa || removed[v] ) continue;
  188.         dfs(v,u);
  189.         subtree[u]+=subtree[v];
  190.     }
  191. }
  192.  
  193. int get_centroid(int u,int papa)
  194. {
  195.     repv(i,adj[u]){
  196.         int v = adj[u][i];
  197.         if(v==papa || removed[v]) continue;
  198.         if( subtree[v] > tot/2 ) return get_centroid(v,u);
  199.     }
  200.     return u;
  201. }
  202.  
  203. void calculate_distance(int u,int papa,int cst,int lev)
  204. {
  205.     dis[lev][u] = cst;
  206.     repv(i,adj[u]){
  207.         int v = adj[u][i];
  208.         if( v==papa || removed[v] ) continue;
  209.         calculate_distance(v,u,cst+1,lev);
  210.     }
  211. }
  212.  
  213. void decompose(int u,int papa,int lev)
  214. {
  215.     tot = 0;
  216.  
  217.     dfs(u,-1);
  218.  
  219.     int center = get_centroid(u,-1);
  220.  
  221.     calculate_distance(center,-1,0,lev);
  222.  
  223.     removed[center] = 1;
  224.     par[center]     = papa;
  225.     level[center]   = lev;
  226.  
  227.     repv(i,adj[center]){
  228.         int v =  adj[center][i];
  229.         if( removed[v] ) continue;
  230.         decompose(v,center,lev+1);
  231.     }
  232.  
  233. }
  234.  
  235. void update(int u) {
  236.     int v = u ,lev = level[u];
  237.     while(v!=-1) {
  238.         res[v] = min(res[v],dis[lev][u]);
  239.         v = par[v];
  240.         lev--;
  241.     }
  242. }
  243.  
  244. int query(int u){
  245.  
  246.     int v   = u;
  247.     int lev = level[u];
  248.     int ret = inf;
  249.     while(v!=-1){
  250.         ret = min(ret,res[v]+dis[lev][u]);
  251.         v = par[v];
  252.         lev--;
  253.     }
  254.     return ret;
  255. }
  256.  
  257.  
  258. int main()
  259. {
  260.     DII(n,m);
  261.  
  262.     rep(i,1,n-1) {
  263.         DII(x,y);
  264.         adj[x].push_back(y);
  265.         adj[y].push_back(x);
  266.     }
  267.  
  268.     decompose(1,-1,0);
  269.  
  270.     fill(res+1,res+1+n,inf);
  271.  
  272.     update(1);
  273.  
  274.     rep(i,1,m)
  275.     {
  276.         DII(c,x);
  277.         if(c==1)    update(x);
  278.         else        PI(query(x));
  279.     }
  280.  
  281.  
  282.     return  0;
  283. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!