Hi, I need help to understand why my code is giving me WA in the following problem Kingdom Roadmap.

Basically the problem ask the following: Given a tree of size N, what's the minimum number of additional edges (and which ones) so the tree becomes a biconected graph (there is no bridge). Notice that an existing edge could be repeated

I will explain my idea part by part, so I hope someone could find my mistake.

The case with N == 2 This is a special case, just print "1\n1 2\n"

N>2 then the tree will have L leaves with L<N

The key observation of my idea is that each leaf of the tree must be connected by at least one of the new edges. Why? because in the contrary case the edges between the leaf and his parent becomes a bridge. So, a lower bound of the answer will be (L + 1) / 2 (integer division).

When we join two leaves u and v with and edge, all the edges in the path from u to v are no longer bridges. Is there some way to match leaves with just (L + 1) / 2 edges and solve the problem?

I think it's posible.

1 Find a node which isn't a leaf and has the following property: If we use this node as the root of the tree, then the maximum quantity of leaves in the subtrees of his neighbors is <= L/2. This node is kind of a "centroid" of leaves.

At the beginning I wasn't sure if there is always a node which has the previos property but I couldn't prove it. I tried to send a code in which if there isn't a "centroid" the program enters in a infinite loop, but the judge still gives WA and not TLE.

2 Using the centroid as a root of the tree, I assign a different color for each of his neighbors and propagate that color to their respective subtrees.

The fact that I used for my solution is that the path between two leaves of different colors must contain the centroid/root. So, if we match each of the leaves with another one that has different color, all the paths from each leaf to the root will no longer be bridges, so the problem is solved. Now, how to assign the necessary edges?

3 Put all the leaves in a vector and sort them by their color. So, all the leaves with the same color will be next to each other. (First assume that L%2 == 0).

if the vector is Leaves then, all the leaves in position i, with i < L / 2, and i + L / 2 must have different color. Why? Because we choose the leaf-centroid as the root, and because of its definition the number of leaves with the same color must be <= L/2. So, in the sorted vector, the positions i and i + L / 2 must be different, otherwise there should be L / 2 + 1 leaves with the same color, which is a contradiction.

4 The only remaining case is when L%2==1

In this case we can match all the edges, we will have 1 unmatched edge. But we could match this edge with the root of the tree removing all the remaining edges that were still bridges. But which leaf?

After sorting, I just add the first leaf in the vector at the end, because the first node and the one in de middle have different color.

This is my code, I tried to add comments for better understanding. Hope someone could find my mistake, I sure it is something that, if is not the base idea, will make me feel stupid when I find it.

Thank you.