fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = int(1e9), N = 1e6, M = 21;
  6.  
  7. int n, up[M][N], tin[N], tout[N], p[4 * N], timer;
  8. pair<int, int> t[4 * N];
  9. vector<int> g[N];
  10.  
  11. void push(int now)
  12. {
  13. 	if (p[now] == 0)
  14.     {
  15. 		return;
  16. 	}
  17. 	t[now].first += p[now];
  18. 	if (now * 2 + 2 < 4 * N)
  19. 	{
  20. 		p[now * 2 + 1] += p[now];
  21. 		p[now * 2 + 2] += p[now];
  22. 	}
  23. 	p[now] = 0;
  24. }
  25.  
  26. void update1(int now)
  27. {
  28. 	int l = now * 2 + 1;
  29. 	int r = now * 2 + 2;
  30. 	if (t[l].first > t[r].first)
  31.     {
  32. 		t[now] = t[l];
  33. 	}
  34. 	else if (t[r].first > t[l].first)
  35.     {
  36.         t[now] = t[r];
  37.     }
  38.     else
  39.     {
  40.         t[now] = t[l];
  41.         t[now].second += t[r].second;
  42. 	}
  43. }
  44.  
  45. void change(int now, int l, int r, int pos, int val)
  46. {
  47. 	push(now);
  48. 	if (l == r)
  49.     {
  50. 		t[now] = {val, 1};
  51. 		return;
  52. 	}
  53. 	int mid = (l + r) / 2;
  54. 	if (pos <= mid)
  55. 	{
  56. 		change(now * 2 + 1, l, mid, pos, val);
  57. 	}
  58. 	else
  59.     {
  60. 		change(now * 2 + 2, mid + 1, r, pos, val);
  61. 	}
  62. 	push(now * 2 + 1);
  63. 	push(now * 2 + 2);
  64. 	update1(now);
  65. }
  66.  
  67. void update(int now, int l, int r, int tl, int tr, int val)
  68. {
  69.     if (tl > tr)
  70.     {
  71.         return;
  72.     }
  73. 	push(now);
  74. 	if (l == tl && r == tr)
  75.     {
  76. 		p[now] += val;
  77. 		push(now);
  78. 		return;
  79. 	}
  80. 	int mid = (l + r) / 2;
  81. 	update(now * 2 + 1, l, mid, tl, min(mid, tr), val);
  82. 	update(now * 2 + 2, mid + 1, r, max(tl, mid + 1), tr, val);
  83. 	push(now * 2 + 1);
  84. 	push(now * 2 + 2);
  85. 	update1(now);
  86. }
  87.  
  88. void dfs(int v, int p = 0)
  89. {
  90. 	tin[v] = timer++;
  91. 	up[0][v] = p;
  92. 	for(int i = 1; i < M; i++)
  93. 	{
  94.         up[i][v] = up[i - 1][up[i - 1][v]];
  95.     }
  96. 	for(int i = 0; i < g[v].size(); i++)
  97. 	{
  98. 		int u = g[v][i];
  99. 		if (u != p)
  100.         {
  101. 			dfs(u, v);
  102. 		}
  103. 	}
  104. 	tout[v] = timer++;
  105. }
  106.  
  107. bool anc(int p, int v)
  108. {
  109. 	return tin[p] <= tin[v] && tout[v] <= tout[p];
  110. }
  111.  
  112. int dist(int v1, int v2)
  113. {
  114.     if (anc(v1, v2))
  115.     {
  116.  	    return 0;
  117.     }
  118. 	int ans = 0;
  119. 	for (int i = M - 1; i >= 0; i--)
  120. 	{
  121. 		if (!anc(up[i][v1], v2))
  122. 		{
  123. 			ans += (1 << i);
  124. 			v1 = up[i][v1];
  125. 		}
  126. 	}
  127. 	return ans + 1;
  128. }
  129.  
  130. int lca(int v1, int v2)
  131. {
  132. 	for (int i = M - 1; i >= 0; i--)
  133. 	{
  134. 		if (!anc(up[i][v1], v2))
  135.         {
  136. 			v1 = up[i][v1];
  137. 		}
  138. 	}
  139. 	return v1;
  140. }
  141.  
  142. int main()
  143. {
  144.     ios_base::sync_with_stdio(0);
  145.     cin.tie(0);
  146.     cout.tie(0);
  147.     cin >> n;
  148.     n++;
  149. 	for(int i = 1; i < n; i++)
  150. 	{
  151. 		int x;
  152. 		cin >> x;
  153. 		x--;
  154. 		g[i].push_back(x);
  155. 		g[x].push_back(i);
  156. 	}
  157. 	for (int i = 0; i < N * 4; i++)
  158.     {
  159.         t[i] = {-INF, 0};
  160.     }
  161.     dfs(0);
  162. 	pair<int, int> c = {0, -1};
  163. 	change(0, 0, 2 * n - 1, tin[0], 0);
  164. 	for(int i = 1; i < n; i++)
  165. 	{
  166. 		int cd = t[0].first;
  167. 		int v = i;
  168. 		int nd = dist(v, c.first) + dist(c.first, v);
  169. 		if (c.second != -1)
  170.         {
  171. 			int nd2 = dist(v, c.second) + dist(c.second, v);
  172. 			if (nd2 < nd)
  173.             {
  174. 				nd = nd2;
  175. 				swap(c.first, c.second);
  176. 			}
  177. 		}
  178. 		change(0, 0, 2 * n - 1, tin[v], nd);
  179. 		if (nd > cd)
  180.         {
  181.             pair<int, int> nc;
  182.             if (c.second != -1)
  183.             {
  184.                 nc = {c.first, -1};
  185.                 if (anc(c.first, c.second))
  186.                 {
  187.                     update(0, 0, 2 * n - 1, tin[c.second], tout[c.second], 1);
  188.                 }
  189.                 else
  190.                 {
  191.                     if (c.first > 0)
  192.                     {
  193.                         update(0, 0, 2 * n - 1, 0, tin[c.first] - 1, 1);
  194.                     }
  195.                     if (c.first < 2 * n - 1)
  196.                     {
  197.                         update(0, 0, 2 * n - 1, tout[c.first] + 1, 2 * n - 1, 1);
  198.                     }
  199.                 }
  200.             }
  201.             else
  202.             {
  203.                 if (anc(c.first, v))
  204.                 {
  205.                     nc = {lca(v, c.first), c.first};
  206.                 }
  207.                 else
  208.                 {
  209.                     nc = {up[0][c.first], c.first};
  210.                 }
  211.                 if (anc(nc.first, nc.second))
  212.                 {
  213.                     if (nc.second > 0)
  214.                     {
  215.                         update(0, 0, 2 * n - 1, 0, tin[nc.second] - 1, -1);
  216.                     }
  217.                     if (nc.second < 2 * n - 1)
  218.                     {
  219.                         update(0, 0, 2 * n - 1, tout[nc.second] + 1, 2 * n - 1, -1);
  220.                     }
  221.                 }
  222.                 else
  223.                 {
  224.                     update(0, 0, 2 * n - 1, tin[nc.first], tout[nc.first], -1);
  225.                 }
  226.             }
  227.             c = nc;
  228.         }
  229.         cout << t[0].second << "\n";
  230. 	}
  231.     return 0;
  232. }
Success #stdin #stdout 0.02s 176192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5tXC92
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!