Guest User

Untitled

a guest
Apr 6th, 2020
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _USE_MATH_DEFINES
  2. #include<iostream>
  3. #include<fstream>
  4. #include<string>
  5. #include<vector>
  6. #include<utility>
  7. #include<algorithm>
  8. #include<climits>
  9. #include<set>
  10. #include<map>
  11. #include<cmath>
  12. #include<iomanip>
  13. #include<iterator>
  14. #include<queue>
  15. #include<stack>
  16. #include<cctype>
  17. #include<deque>
  18. #include<time.h>
  19. #include<bitset>
  20. #include<random>
  21. #include<unordered_set>
  22. #include<unordered_map>
  23. #include<sstream>
  24. #include<random>
  25. #include<numeric>
  26. //by Skeef79
  27.  
  28. typedef long long ll;
  29. typedef long double ld;
  30.  
  31. typedef unsigned long long ull;
  32.  
  33. #pragma warning(disable : 4996)
  34. #pragma comment(linker, "/STACK:16777216")
  35. #define pb push_back
  36. #define en '\n'
  37. #define for0(i,n) for(int i = 0;i<n;i++)
  38. #define all(x) (x).begin(),(x).end()
  39. #define rall(x) (x).rbegin(),(x).rend()
  40. #define vec vector
  41. #define pii pair<int,int>
  42. #define pll pair<ll,ll>
  43. #define what_is(x) cout<<#x<<" is "<<x<<en;
  44.  
  45. using namespace std;
  46.  
  47. const int INF = 2000000000;
  48. const ll LINF = 2000000000000000000;
  49.  
  50. template<typename T> void print(vector<T>& a)
  51. {
  52. for (int i = 0; i < a.size(); i++)
  53. cout << a[i] << ' ';
  54. cout << en;
  55. }
  56.  
  57. template<typename T> void print(deque<T>& a)
  58. {
  59. for (int i = 0; i < a.size(); i++)
  60. cout << a[i] << ' ';
  61. cout << en;
  62. }
  63.  
  64. template<typename T> void print(vector<vector<T>>& a)
  65. {
  66. for (int i = 0; i < a.size(); i++)
  67. {
  68. for (int j = 0; j < a[i].size(); j++)
  69. cout << a[i][j] << ' ';
  70. cout << en;
  71. }
  72. }
  73.  
  74. template <typename T> void input(vector<T>& a)
  75. {
  76. for (int i = 0; i < a.size(); i++)
  77. cin >> a[i];
  78. }
  79.  
  80. template<typename T> void input(deque<T>& a)
  81. {
  82. for (int i = 0; i < a.size(); i++)
  83. cin >> a[i];
  84. }
  85.  
  86. template<typename T> void input(vector<vector<T>>& a)
  87. {
  88. for (int i = 0; i < a.size(); i++)
  89. for (int j = 0; j < a[i].size(); j++)
  90. cin >> a[i][j];
  91.  
  92. }
  93. int n, m, K = 365;
  94. const int LOG = 17;
  95.  
  96. vector<vector<int>>g;
  97. vector<int>d;
  98. vector<bool>c;
  99. vector<int>lvl;
  100. vector<vector<int>>jump;
  101. vector<int> added;
  102.  
  103. void dfs(int v, int p = 0, int level = 0)
  104. {
  105. jump[v][0] = p;
  106. lvl[v] = level;
  107. for (int to : g[v])
  108. if (to != p)
  109. dfs(to, v, level + 1);
  110. }
  111.  
  112. void initJump()
  113. {
  114. for (int k = 1; k < LOG; k++)
  115. for (int v = 0; v < n; v++)
  116. jump[v][k] = jump[jump[v][k - 1]][k - 1];
  117. }
  118.  
  119. void initLCA()
  120. {
  121. lvl = vector<int>(n);
  122. jump = vector<vector<int>>(n, vector<int>(LOG));
  123. dfs(0);
  124. initJump();
  125. }
  126.  
  127. int lca(int u, int v)
  128. {
  129. if (lvl[u] > lvl[v])
  130. swap(u, v);
  131. for (int k = LOG - 1; k >= 0; k--)
  132. if (lvl[u] <= lvl[jump[v][k]])
  133. v = jump[v][k];
  134.  
  135. if (u == v)
  136. return v;
  137. for (int k = LOG - 1; k >= 0; k--)
  138. if (jump[v][k] != jump[u][k])
  139. {
  140. v = jump[v][k];
  141. u = jump[u][k];
  142. }
  143.  
  144. return jump[u][0];
  145. }
  146.  
  147. void rebuild()
  148. {
  149. fill(all(d), INF);
  150. queue<int>q;
  151. for (int v = 0; v < n; v++)
  152. if (c[v])
  153. {
  154. d[v] = 0;
  155. q.push(v);
  156. }
  157.  
  158. while (!q.empty())
  159. {
  160. int v = q.front();
  161. q.pop();
  162. for (int to : g[v])
  163. if (d[v] + 1 < d[to])
  164. {
  165. d[to] = d[v] + 1;
  166. q.push(to);
  167. }
  168. }
  169.  
  170. }
  171.  
  172. int path(int u, int v)
  173. {
  174. return lvl[u] + lvl[v] - 2 * lvl[lca(u, v)];
  175. }
  176.  
  177. int query(int v)
  178. {
  179. int ans = d[v];
  180. for (int to : added)
  181. ans = min(ans, path(v, to));
  182. return ans;
  183. }
  184.  
  185. void solve()
  186. {
  187. scanf("%d%d", &n, &m);
  188. g = vector<vector<int>>(n);
  189. d = vector<int>(n,INF);
  190. c = vector<bool>(n);
  191. added.reserve(K);
  192. c[0] = true;
  193.  
  194. for (int i = 0; i < n - 1; i++)
  195. {
  196. int u, v;
  197. scanf("%d%d", &u, &v);
  198. u--, v--;
  199. g[u].pb(v);
  200. g[v].pb(u);
  201. }
  202. rebuild();
  203. initLCA();
  204. int type, v;
  205.  
  206. for (int i = 0; i < m; i++)
  207. {
  208. if (i%K == 0)
  209. {
  210. rebuild();
  211. added.clear();
  212. }
  213. scanf("%d%d", &type, &v);
  214.  
  215. if (type == 1)
  216. {
  217. added.pb(v - 1);
  218. c[v - 1] = true;
  219. }
  220. else
  221. printf("%d\n",query(v - 1));
  222. }
  223.  
  224. }
  225.  
  226. int main()
  227. {
  228. ios::sync_with_stdio(false);
  229. cin.tie(0);
  230. cout.tie(0);
  231.  
  232. #ifdef _DEBUG
  233. freopen("input.txt", "r", stdin);
  234. #endif
  235.  
  236. int tst = 1;
  237. //cin >> tst;
  238. while (tst--)
  239. solve();
  240.  
  241. }
RAW Paste Data