×

CLERVT - Editorial

Author and Editorialist: Soumik Sarkar
Tester: Sarthak Manna

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 XOR-sum 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_{x-1}, 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_{x-1}, 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.

ans = N - 1
x = last set bit in mask
if x is the only set bit in mask:
ans = ans XOR (N - 1 - dp[mask])
else:
y = second last set bit in mask
ans = ans XOR ((N - 1 - (dp[mask] + dist(G[x], 1)) / 2)


Note: The solution requires finding the last (or first) 2 set bits in an integer which can be done quickly in GCC using __builtin_ctz. If you instead find the set bits by looping over each bit position it appears to take $\mathcal{O}(K)$ time for each subset but with a little thought it can be shown that the total operations required over all subsets remains $\mathcal{O}(2^K)$.

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_{K-1}, 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 $N-1$, 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
Solution by @filyan: 18287756

AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here
Tester's solution can be found here.

6★meooow ♦
7.0k718
accept rate: 48%

19.7k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×2,557
×2,086
×281
×73
×53
×6

question asked: 16 Apr '18, 00:44

question was seen: 552 times

last updated: 20 Apr '18, 13:57