PROBLEM LINK:Author and Editorialist: Soumik Sarkar DIFFICULTY:MEDIUM PREREQUISITES:Euler tour, Dynamic programming PROBLEM:There is a tree with $N$ vertices, and a set of vertices $G$. For every subset $G'$ of $G$, find the maximum number of edges which can be removed while leaving each vertex in $G'$ connected to vertex $1$. Calculate the XORsum of all these values. EXPLANATION:Consider the tree to be rooted at $1$. Given a set $G$ imagine you have removed all edges are not necessary for the vertices in $G$ to remain connected to $1$. What will this graph look like? Of course the graph will remain a connected tree. Also, all the leaves will belong to $G$. Some elements of $G$ may lie in the interior of the tree as well. If asked to find the number of edges in this tree, you would say the answer is $G  1$. However, in a roundabout way I can also claim that counting the edges on an Euler tour of this tree will give me exactly twice the answer. Let it be that during the Euler tour I start from the root and happen to visit the vertices in $G$ in the order $G_1, G_2, G_3, ... G_K$. I can say the total length of the Euler tour is $dist(1, G_1) + dist(G_1, G_2) + dist(G_2, G_3) + .... + dist(G_K, 1)$. As mentioned before, this is exactly twice the number of edges in the tree, but the values of all these terms are the same as in the original tree. So if we know $dist(G_i, G_j)$ for each pair $(i, j)$ and also the "Euler tour order" of the vertices in $G$, we can calculate the answer in $\mathcal{O}(K)$! We can get the Euler tour order with one dfs from the root. And then we can proceed to make $K$ dfs from each vertex in $G$ to calculate the distance matrix for each pair of vertices in $G$. To get the distance matrix it is also possible to use faster methods, but not necessary. However applying this procedure in this form is too slow as it requires $\mathcal{O}(K)$ time ($K/2$ on average) for each subset of $G$. To optimize it, we can notice that we can use the answer for one subset to calculate that of another. Let us denote by $f(G)$ the value $dist(1, G_1) + dist(G_1, G_2) + ... dist(G_{x1}, G_{x})$ where $G_1$ to $G_x$ are the elements of $G$ in Euler tour order. Then clearly $f(G) = f(G \setminus G_x) + dist(G_{x1}, G_{x})$. Now we can apply dynamic programming using bitmasks to denote subsets and calculate the answer for each subset in constant time and XOR them together.
Note: The solution requires finding the last (or first) 2 set bits in an integer which can be done quickly in GCC using Total complexity is $\mathcal{O}(NK + 2^K)$. ALTERNATE BASIS FOR SOLUTION:Instead of calculating the answer as half of $dist(1, G_1) + dist(G_1, G_2) + ... + dist(G_K, 1)$ one can also claim that the answer is exactly $dist(lca(1, G_1), G_1) + dist(lca(G_1, G_2), G_2) + ... + dist(lca(G_{K1}, G_K), G_K)$, where $lca(u, v)$ is the lowest common ancestor of $u$ and $v$. The rest of the process can be done based on this as well. ALTERNATE SOLUTION:Instead of storing answers to "What is the tree size for a particular subset?" we can instead store "How many subsets have a particular tree size"? This is a better way because the number of unique sizes is bounded by $N1$, whereas the number of subsets is much greater. Let $f(i, d)$ be the number of subsets that have $G_i$ as last element and tree size exactly equal to $d$. Then for any $G_j$ for $j > i$, the value of $f(i, d)$ directly contributes to $f(j, d + dist(lca(G_i, G_j), G_j))$. Here dynamic programming can be used in the "forward" manner, to get a solution in $\mathcal{O}(NK^2)$. Solution by @uwi: 18276897 AUTHOR'S AND TESTER'S SOLUTION:Author's solution can be found here asked 16 Apr '18, 00:44
