Hi,
Has anybody been able to understand this CODEFORCES problem. I have read the editorial and I still have no clue what the author has been trying to say. It would be really good if someone can give a detailed explanation about this problem.
I try to explain…
There a 2 key ideas behind this problem
Key idea 1 // Center(s) of tree
*/ a tree has 1 ou 2 centers, depending of D, the longest distance between two nodes. If D is even, there is 1 center, is D is odd there are 2 centers.
*/ if you take two nodes X and Y such that dist(X,Y)=D, then there is a path X --> X1 --X2–X3–>Xn-1–>Y. If you apply the permutation p, then this gives another path with the same length.
*/ so a longest path is mapped to a longest path. So center(s) are fixed or mapped onto each other.
*/ Suppose we have a tree T for which p is a good permutation. If T has a single center, then this center is a fixed point for p. If T has 2 centers, they are fixed, or p swaps them. In any case, to be a good permutation, p needs to have at least 1 fixed points or at least a length 2 permutation (p(a)=b and p(b)=a).
Key idea 2: permutation decomposition into cycles
If there is a fixed point in the permutation. It’s easy. Consider this fixed point as the root of the tree. And link every other node to it. Finished.
If we have no fixed point in p ? We look for a swap (a,b) . Is there is no such swap, then the answer is NO, because we are not able to have centers.
Suppose we have our swap (a,b). It corresponds to 2 values a and b, with p(a)=b and p(b)=a. We set center1=a and center2=b.
Take now another value x, and look at the cycle generated by x. It’s the lenght of {x,p(x),p(p(x))…}.
The key idea is that if the length of x cycle is odd, you will never be able to link x to another point y which has an even cycle.
Why ?
Suppose x cycle length is 3, and y cycle lengh is 2.
Which means, that under p, we have p(x)=x1, p(x1)=x2 p(x2))=x and p(y)=y1 and p(y1)=y.
If x and y are linked (noted as x<–>y), then x1 and y1 are linked (x1<->y1). Thus x2<–>y. Thus x<–>y1 thus x1<–>y. So we have a loop x <—> y <—> x1 <—> y1 <–> x. Impossible because we have a tree.
So now, if there is and odd cycle, answer is NO, the Tree will never be connected: we will connect even cycle togethers, and odd cycle togethers, but will never be able to connect even+odd. As we have both even and odd, this is a show stopper.
If all cycles are even, it s easy to finish. You have two centers a and b. You take x with even cycle. You map a to x, b to p(x). Then a to p(p(x)) and bto p(p(p(x)))). And so on…