## Editorial for IOI '17 P5 - Simurgh

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

#### Simplified Statement

Given a graph with vertices and edges. Zal has selected a spanning tree of the graph, but you do not know which edges appear in his spanning tree. In every query, you can give him a spanning tree of the graph, and he will tell you how many edges your spanning tree has in common with his. You wish to find his spanning tree with a small number of queries.

#### Subtask 1

Iterate over all spanning trees and ask all of them.

#### Subtask 2

Start with an arbitrary spanning tree and keep improving your solution as follows:

- Randomly choose an edge .
- Add the edge to your solution.
- Remove a random edge from the cycle of to make it a tree .
- If has more edges in common with Zal's tree, then set .
- Stop if is Zal's tree.

#### Subtask 3

In this subtask, we can make exactly one query per edge. Decompose your graph into a number of disjoint (or almost disjoint) cycles. For each cycle , find a tree that connects to all vertices of the graph ( is a spanning tree with an extra edge). For each , determine the number of edges that has in common with Zal's tree. If all of these numbers are equal, then none of the edges of appear in Zal's tree. Otherwise, the edges whose removal decrease the number of the common edges are in Zal's tree.

#### Subtask 4

One can determine with queries whether an edge appears in Zal's tree; it only suffices to find other edges that make a triangle together with and do as mentioned earlier. Fix an arbitrary tree and find out which of its edges appear in Zal's tree. Once we find that, for every forest of we can determine how many edges shares with Zal's tree with a single query: add some of the edges of to to make it a spanning tree, query that tree, and determine how many edges of are in common with Zal's tree. Determine the degree of each vertex in Zal's tree with queries. Then we can find the edge connected of each leaf with queries and remove that edge from the solution. We continue with the new edges.

#### Subtask 5

The solution is almost the same as the previous subtask. The only difference is that finding a tree and determining which of its edges appear in Zal's tree is a bit harder. Roughly, we need to remove the cut edges (which we know are included in Zal's tree). Then every component is a -edge-connected graph and we can find an ear-decomposition for them. Note that for every cycle , we can figure out with queries which edges of are in Zal's tree. The only extension that we need to that is that if we already know the status of edges of , we can do this with queries. Therefore, we can solve the problem for each component separately with at most queries.

## Comments