Redaksiya

Group 1: each vertex is connected with at most 2 others (the tree is a bamboo).

Let's note that removing a vertex from a bamboo tree does not stop it from being a bamboo tree, and also that any bamboo tree is a mirror tree. Thus, in this subgroup, it is sufficient to output all the leaves.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Group 2: at most one vertex connected more than with 1 other vertex (the tree is a hedgehog).

Let's note that any hedgehog tree is also a mirror tree. If the number of leaves is even, it is mirrored relative to the central vertex. If the number of leaves is odd, it is mirrored relative to the center/one leaf pair. Thus, in this case, highlighting all the leaves also works.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Group 3: $n\le 50$.

In this and the next group, our algorithm will work as follows: We will iterate through the leaf nodes, remove them, and check the tree for symmetry.

Now let's look at how to check this in more detail:

Notice that if a tree was symmetric, then there are two vertices from which we can reflect (let's call them $u$ and $v$). The only condition is that for each vertex on the path from $u$ to $v$, all distinct subtrees of its children (where neither vertex $u$ nor vertex $v$ are located) must appear an even number of times. It is easy to see that this condition is both necessary and sufficient. To compare different subtrees, we can hash them and then maintain a map that will store the number of occurrences of each hash.

The time complexity of checking for symmetry is $O(n^3\log (n))$. Thus, the total time complexity is $O(n^4\log (n))$.

Time complexity: $O(n^4\log (n))$

Memory complexity: $O(n)$

Group 4: $n\le 100$.

Now we will check for symmetry not in $O(n^3\log (n))$ but in $O(n^2\log (n))$. To do this, notice that it is enough to know one vertex on the symmetric path. Let this be vertex $v$. We will hash all subtrees from it, and now note that there are at most 2 subtrees of vertex $v$ that occur an odd number of times (the subtrees where the endpoints lie). We will start a DFS from vertex $v$ and only visit the vertices whose subtrees occur an odd number of times. Let the function $f(i)$ denote the number of such subtrees of vertex $i$ that occur an odd number of times. If the current vertex is the start, $f(v)\le 2$, otherwise $f(v)\le 1$. Now, we will iterate through this vertex and start our algorithm.

Time complexity: $O(n^3\log (n))$

Memory complexity: $O(n)$

Group 5: $n\le 1000$.

Notice that the centroid will always lie on the symmetric path. We will prove this by contradiction: Assume this is not the case, then the centroid lies in one of the parts relative to our symmetric path. However, since our tree is symmetric, there must also be a centroid in the other half. However, these two centroids are not adjacent since there must be a vertex from the symmetric path between them. This is a contradiction. This means that we simply run the solution for the previous group by checking only one vertex.

Time complexity: $O(n^2\log (n))$

Memory complexity: $O(n)$

Group 6: no additional constraints.

For the full solution, we cannot use the previous algorithm, so we will do something different. First, notice that the centroid after removing one vertex will at most shift to an adjacent vertex, and only to the largest subtrees. That is, we have no more than 3 or 4 different vertices that will be on the symmetric path after removing any of the leaves. We will iterate through these vertices, let the current one be $c$.

We will root our tree at vertex $c$. Let's build a DP $d{p}_v$ that will store $true$ if the subtree of $v$ can be symmetric starting from vertex $v$ and ending at some other vertex, and $false$ otherwise. The update will be as follows. If $f(v)>1$, then $d{p}_v=false$. If $f(v)=1$, then take any of its occurrences (let its root (i.e., the child of $v$) be $u$), $d{p}_v=d{p}_u$. If $f(v)=0$, then $d{p}_v=true$.

Another auxiliary function that we will need is to check if the subtree of vertex $v$ can be transformed into the subtree of vertex $u$. As a good optimization, we can immediately check that the size of the subtree of $v$ is 1 more than the subtree of $u$. Otherwise, look at the multiset of the first vertex (let this be $A$) and the second vertex (let this be $B$), then look at the sets $C=(A\setminus (A\cap B))$ and $D=(B\setminus (A\cap B))$. If $|C|>1$ or $|D|>1$, then the answer is immediately no. Otherwise, we proceed recursively, maintaining an array of identical subtrees.

Let's write a DFS that will traverse the subtree and add all vertices that can be removed. Suppose we are at vertex $v$. Consider several cases: 1. $f(v)=0$; we can simply recurse into all vertices.

2. $f(v)=1$; we either recurse into this odd vertex or iterate over a vertex $u$ such that $d{p}_u=true$ and we can transform this subtree into our odd one.

3. $f(v)=2$; we must make them identical since there cannot be more than one odd subtree, and then just break;

4. $f(v)=3$; this is handled similarly to the previous case.

5. $f(v)>3$; we can just break, cause it is imposible to leave only one odd subtree.

This works in linear time, beacuse if we need to do checks(that take linear time), we will break after it.

For $c$, there are a few more cases, but they are also not difficult to handle. There is one small edge case related to subtrees of size 1, which needs to be handled carefully.

Time complexity: $O(n\log (n))$

Memory complexity: $O(n)$