fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int kMaxN = 1e6;
  6.  
  7. class SemiRing {
  8.   public:
  9. 	SemiRing(int el=0) : el_(el) {}
  10. 	SemiRing& operator +=(const SemiRing& rhs) {
  11. 		// u + v = min(u, v);
  12. 		if (el_ > rhs.el_) {
  13. 			el_ = rhs.el_;
  14. 		}
  15. 		return *this;
  16. 	}
  17. 	SemiRing& operator *=(const SemiRing& rhs) {
  18. 		// u * v = u + v
  19. 		el_ += rhs.el_;
  20. 		if (el_ > inf) {
  21. 			el_ = inf;
  22. 		}
  23. 		return *this;
  24. 	}
  25. 	SemiRing operator +(const SemiRing& rhs) const { return SemiRing(*this) += rhs; }
  26. 	SemiRing operator *(const SemiRing& rhs) const { return SemiRing(*this) *= rhs; }
  27. 	int value() const { return el_; }
  28.   public:
  29. 	static constexpr int inf = 0x3f3f3f3f;
  30.   private:
  31. 	int el_;
  32. };
  33.  
  34. class Mat22 {
  35.   public:
  36. 	Mat22(SemiRing x00=0, SemiRing x01=SemiRing::inf, SemiRing x10=0, SemiRing x11=SemiRing::inf)
  37. 		: a00(x00), a01(x01), a10(x10), a11(x11) {}
  38. 	Mat22 operator *=(const Mat22& rhs) {
  39. 		return *this = *this * rhs;
  40. 	}
  41. 	Mat22 operator *(const Mat22& rhs) const {
  42. 		// Normal matrix multiplication.
  43. 		return Mat22(
  44. 			a00 * rhs.a00 + a01 * rhs.a10,
  45. 			a00 * rhs.a01 + a01 * rhs.a11,
  46. 			a10 * rhs.a00 + a11 * rhs.a10,
  47. 			a10 * rhs.a01 + a11 * rhs.a11);
  48. 	}
  49. 	int Get00() const { return a00.value(); }
  50. 	int Get01() const { return a01.value(); }
  51. 	int Get10() const { return a10.value(); }
  52. 	int Get11() const { return a11.value(); }
  53. 	friend ostream& operator <<(ostream& os, const Mat22& rhs) {
  54. 		os << "{ { " << rhs.a00.value() << " " << rhs.a01.value() << " }, ";
  55. 		os << "{ " << rhs.a10.value() << " " << rhs.a11.value() << " } }";
  56. 		return os;
  57. 	}
  58.   private:
  59. 	SemiRing a00, a01, a10, a11;
  60. };
  61.  
  62.  
  63. int n;
  64. int next_idx;
  65. vector<int> graph[kMaxN];
  66. int weight[kMaxN], parent[kMaxN], head[kMaxN], bottom[kMaxN], vid[kMaxN];
  67. Mat22 tree[2 * kMaxN], light_value[kMaxN];
  68. int last_skip[kMaxN], last_take[kMaxN];
  69.  
  70. int GetId(int l, int r) {
  71. 	return (l + r) | (l != r);
  72. }
  73.  
  74. // Range query: Product of. matrices.
  75. Mat22 Query(int l, int r, int q_l, int q_r) {
  76. 	int id = GetId(l, r);
  77. 	if (q_l <= l and r <= q_r) {
  78. 		return tree[id];
  79. 	} else {
  80. 		int m = (l + r) / 2;
  81. 		if (q_r <= m) {
  82. 			return Query(l, m, q_l, q_r);
  83. 		} else if (q_l > m) {
  84. 			return Query(m + 1, r, q_l, q_r);
  85. 		} else {
  86. 			return Query(l, m, q_l, q_r) * Query(m + 1, r, q_l, q_r);
  87. 		}
  88. 	}
  89. }
  90.  
  91. // Initialise segment tree.
  92. void BuildTree(int l, int r) {
  93. 	int id = GetId(l, r);
  94. 	if (l == r) {
  95. 		tree[id] = light_value[l];
  96. 	} else {
  97. 		int m = (l + r) / 2;
  98. 		BuildTree(l, m);
  99. 		BuildTree(m + 1, r);
  100. 		tree[id] = tree[GetId(l, m)] * tree[GetId(m + 1, r)];
  101. 	}
  102. }
  103.  
  104. // Point update: Update the leaf value for a node.
  105. void Update(int l, int r, int pos) {
  106. 	int id = GetId(l, r);
  107. 	if (l == r) {
  108. 		tree[id] = light_value[l];
  109. 	} else {
  110. 		int m = (l + r) / 2;
  111. 		if (pos <= m) {
  112. 			Update(l, m, pos);
  113. 		} else {
  114. 			Update(m + 1, r, pos);
  115. 		}
  116. 		tree[id] = tree[GetId(l, m)] * tree[GetId(m + 1, r)];
  117. 	}
  118. }
  119.  
  120. Mat22 PathValue(int node) {
  121. 	// {{a b} {c d}} * {{0 inf} {0 inf}} = {{min(a, b) inf} {min(c, d) inf}}
  122. 	// try attaching a dummy empty heavy node: {{0 inf} {0 inf}}
  123. 	// as we always added a light leaf in the path.
  124. 	return Query(0, n - 1, vid[head[node]], bottom[head[node]]) * Mat22(0, SemiRing::inf, 0, SemiRing::inf);
  125. }
  126.  
  127. void LightLeaf(int node) {
  128. 	// append the leaf node to the end of HLD path till now.
  129. 	bottom[head[node]] = vid[node];
  130. 	// Traverse till you reach the HLD path containing root i.e. 1.
  131. 	while (parent[head[node]] != -1) {
  132. 		// Update the HLD path containing node. This is characterised by
  133. 		// head[node].
  134. 		node = head[node];
  135. 		// Find product of matrices in the HLD path.
  136. 		auto val = PathValue(node);
  137. 		// Find the parent_idx for updating its matrix later.
  138.  
  139. 		// Refer to example matrices in editorial to understand how the calculations
  140. 		// look like.
  141. 		int parent_idx = vid[parent[node]];
  142. 		int add_skip = val.Get00() - last_skip[node];
  143. 		int add_take = val.Get10() - last_take[node];
  144. 		int parent_skip = light_value[parent_idx].Get00() + add_skip - 1;
  145. 		int parent_take = light_value[parent_idx].Get01() + add_take;
  146.  
  147. 		// Similar to solution for 41 points, persist the value for the changes we
  148. 		// did to this chain till now.
  149. 		last_skip[node] += add_skip;
  150. 		last_take[node] += add_take;
  151.  
  152. 		// General Matrix is {{1 + g(u), f(u)} {1 + g(u), inf}}
  153. 		// where f(u) means "u" is definitely taken.
  154. 		light_value[parent_idx] = Mat22(parent_skip + 1, parent_take, parent_skip + 1, SemiRing::inf);
  155.  
  156. 		// Update the matrix for the parent as a new child was added.
  157. 		Update(0, n - 1, parent_idx);
  158. 		// Change the chain.
  159. 		node = parent[node];
  160. 	}
  161. }
  162.  
  163. // Subtree sum.
  164. void FindWeights(int node) {
  165. 	weight[node] = 1;
  166. 	for (auto&& son : graph[node]) {
  167. 		FindWeights(son);
  168. 		weight[node] += weight[son];
  169. 	}
  170. }
  171.  
  172. // HLD decomposition.
  173. // vid[node] = position in HLD array
  174. // head[node] = node from which HLD path containing "node" begins.
  175. // There are 2 ways to decompose.
  176. // 1. Either based on the largest subtree.
  177. // 2. Or decompose every subtree expect the one containing atleast half of the
  178. // nodes.
  179. void Decompose(int node, int path_head) {
  180. 	vid[node] = next_idx++; head[node] = path_head;
  181. 	for (auto&& son : graph[node]) {
  182. 		if (weight[node] < 2 * weight[son]) {
  183. 			// Heavy-child
  184. 			Decompose(son, path_head);
  185. 		}
  186. 	}
  187. 	for (auto&& son : graph[node]) {
  188. 		if (weight[node] >= 2 * weight[son]) {
  189. 			// Light-child, start a new chain.
  190. 			Decompose(son, son);
  191. 		}
  192. 	}
  193. }
  194.  
  195. int BoatSize(int num_nodes, int mvc) {
  196. 	if (num_nodes <= 3) {
  197. 		// base case.
  198. 		return 2;
  199. 	}
  200. 	if (mvc == 1) {
  201. 		// Special case: star graph.
  202. 		return 3;
  203. 	}
  204. 	// include chef in minimum vertex cover.
  205. 	return 1 + mvc;
  206. }
  207.  
  208. int main() {
  209. 	cin.tie(0);
  210. 	ios_base::sync_with_stdio(false);
  211. 	int num_tests; cin >> num_tests;
  212. 	while (num_tests--> 0) {
  213. 		// O-based indexing is used in the solution.
  214. 		// Input.
  215. 		cin >> n;
  216. 		parent[0] = -1;
  217. 		for (int i = 1; i < n; ++i) {
  218. 			cin >> parent[i]; --parent[i];
  219. 			graph[parent[i]].push_back(i);
  220. 		}
  221. 		// Subtree sum.
  222. 		FindWeights(0);
  223. 		// HLD decompostion.
  224. 		Decompose(0, 0);
  225. 		// Base values for leaves.
  226. 		for (int i = 0; i < n; ++i) {
  227. 			// Unity matrix as discussed in editorial.
  228. 			light_value[i] = Mat22(1, 0, 1, SemiRing::inf);
  229. 		}
  230. 		// Initialise Segment tree.
  231. 		BuildTree(0, n - 1);
  232. 		// Insert root node 1.
  233. 		LightLeaf(0);
  234. 		for (int i = 1; i < n; ++i) {
  235. 			// Insert leaves one by one.
  236. 			LightLeaf(i);
  237. 			cout << BoatSize(i + 1, PathValue(0).Get00()) << " \n"[i == n - 1];
  238. 		}
  239. 		// Clear.
  240. 		next_idx = 0;
  241. 		for (int i = 0; i < n; ++i) {
  242. 			graph[i].clear();
  243. 			last_skip[i] = 0;
  244. 			last_take[i] = 0;
  245. 		}
  246. 	}
  247. }
Success #stdin #stdout 0.04s 73400KB
comments (?)
stdin
copy 
2
7
1 1 2 2 3 5
16
1 1 2 2 3 3 4 4 5 6 6 6 1 11 11
stdout
copy 
2 2 3 3 3 4
2 2 3 3 3 3 4 4 5 6 6 6 6 7 7
https://ideone.com/s0Rkg3
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!