Advertisement
Guest User

Untitled

a guest
Nov 13th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAXN 70100
  6. #define K 300
  7. #define INF 2100000000LL
  8. #define MAXBLOCKS 300
  9. //#define int long long
  10. typedef long long LL;
  11.  
  12. int N;
  13. vector<int> adj[MAXN];
  14.  
  15. //leafdist
  16. int L[MAXN], D[MAXN];
  17. int cnt = 0;
  18. bool vis[MAXN];
  19. int in[MAXN], out[MAXN];
  20.  
  21. void leafDfs(int n, int p=0){
  22. D[n] = D[p] + 1;
  23. if(!vis[n]){
  24. vis[n] = true;
  25. in[n] = cnt;
  26. cnt++;
  27. }
  28. for(int v : adj[n])
  29. if(v != p){
  30. leafDfs(v, n);
  31. L[n] = min(L[n], L[v] + 1);
  32. }
  33. out[n] = cnt;
  34. }
  35.  
  36. void leafDfs2(int n, int p=0){
  37. L[n] = min(L[n], L[p] + 1);
  38. for(int v : adj[n])
  39. if(v != p)
  40. leafDfs2(v, n);
  41. }
  42.  
  43. //BIT stuff
  44. int BIT[MAXBLOCKS][2*MAXN];
  45. int ans[MAXN];
  46.  
  47. void add(int i, int val, int block){
  48. for(i+=N; i < 2*MAXN; i += (i & -i))
  49. BIT[block][i] += val;
  50. }
  51.  
  52. LL get(int i, int block){
  53. LL ret = 0;
  54. for(i+=N; i > 0; i -= (i & -i))
  55. ret += BIT[block][i];
  56. return ret;
  57. }
  58.  
  59. //answer dfs
  60. int key[MAXN];
  61. int val[MAXN];
  62. int lazy[MAXBLOCKS];
  63. int overall_lazy;
  64.  
  65. inline void resetTable(int x){
  66. for(int i = x*K; i < min(N, x*K+K); i++)
  67. add(key[i], -val[i], x);
  68. }
  69.  
  70. inline void createTable(int x){
  71. for(int i = x*K; i < min(N, x*K+K); i++)
  72. add(key[i], val[i], x);
  73. }
  74.  
  75. inline void addDepths(int l, int r, int val){
  76. for(int i = l; i <= r; i++)
  77. key[i] += val;
  78. }
  79.  
  80. inline void update(int l, int r, int val){
  81. int ls = l / K;
  82. int rs = r / K;
  83. //reset table, update D, refill
  84. if(ls == rs){
  85. resetTable(ls);
  86. addDepths(l, r, val);
  87. createTable(ls);
  88. }
  89. else{
  90. // return;
  91. //left
  92. resetTable(ls);
  93. addDepths(l, ls*K+K, val);
  94. createTable(ls);
  95. //middle
  96. for(int i = ls + 1; i < rs; i++)
  97. lazy[i] += val;
  98. //right
  99. resetTable(rs);
  100. addDepths(rs*K, r, val);
  101. createTable(rs);
  102. }
  103. }
  104.  
  105. inline void dfs(int n, int p){
  106. //calculate answer for this node
  107. for(int i = 0; i <= N / K; i++)
  108. ans[n] += get(-lazy[i]-overall_lazy, i);
  109. for(int v : adj[n]){
  110. if(v != p){
  111. overall_lazy--;
  112. update(in[v], out[v]-1, 2);
  113. dfs(v, n);
  114. overall_lazy++;
  115. update(in[v], out[v]-1, -2);
  116. }
  117. }
  118. }
  119.  
  120.  
  121. int main() {
  122. freopen("atlarge.in", "r", stdin); freopen("atlarge.out", "w", stdout);
  123. cin >> N;
  124. //K = sqrt(N); // the size of each block
  125. for(int i = 0; i < N-1; i++){
  126. int a, b;
  127. cin >> a >> b;
  128. adj[a].push_back(b);
  129. adj[b].push_back(a);
  130. }
  131. //calculate leafdist, dfs order, and depths
  132. for(int i = 0; i <= N; i++){
  133. if(adj[i].size() == 1)
  134. L[i] = 0;
  135. else
  136. L[i] = INF;
  137. }
  138. D[0] = -1;
  139. leafDfs(1);
  140. leafDfs2(1);
  141. for(int i = 1; i <= N; i++){
  142. key[in[i]] = L[i] - D[i];
  143. val[in[i]] = 2 - (int)adj[i].size();
  144. }
  145. //initialize the BIT tables
  146. for(int i = 0; i <= N / K; i++)
  147. createTable(i);
  148. //dfs from node 1, update BITs as you go
  149. dfs(1, 0);
  150. for(int i = 1; i <= N; i++) {
  151. if(adj[i].size() == 1)
  152. cout << 1 << endl;
  153. else
  154. cout << ans[i] << endl;
  155. }
  156. // cout << 3 << endl << 1 << endl << 3 << endl << 3 << endl << 3 << endl << 1 << endl << 1;
  157. // cout << endl;
  158. // for(int i = 1; i <= N; i++)
  159. // cout << setw(3) << i;
  160. // cout << endl;
  161. // for(int i = 1; i <= N; i++)
  162. // cout << setw(3) << in[i];
  163. // cout << endl;
  164. // for(int i = 0; i < N; i++)
  165. // cout << setw(3) << rin[i];
  166. // cout << endl;
  167. // cout << "K: " << K << endl;
  168. // for(int i = 1; i <= N; i++)
  169. // cout << setw(3) << L[i] - D[i];
  170. // cout << endl;
  171. // for(int i = 1; i <= N; i++)
  172. // cout << setw(3) << 2-(int)adj[i].size();
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement