Hello everyone!

I recently come across an interesting tree problem.

There is an undirected tree, T, with edges of length 1. Initially, each of the nodes stores a value equal to the node number. Shuffle these values among the nodes in such a way that no node stores a value equal to its node number. There are two values to determine:

1) The minimum possible sum of the distances between the initial and final positions of all values.

2) The maximum possible sum of the distances between the initial and final positions of all values.

1<=number of nodes<=1e5.

I was able to solve the case of minimum possible sum by applying maximum matching. But I am not able to come up with an efficient solution for 2nd case. I am also struggling to prove its correctness for the n^2 solution(my intution is repatedly finding diameter and swapping the node at diameter and removing them after adding their distances). I discussed the probelm with many of my friends(some are CMs) but we are not able to come up with efficient algo for second case.

It would be great if someone can help in solving the second case.

Hi everyone!

I recently come across this interesting topic of Round-Square Tree in the solution for the recent AtCoder Beginner Contest. This is the link for the editorial which refers the concept.

I find the idea interesting as it is simpler than the official solution which uses network flow. But I couldn't find much resources on the topic online.

So if anybody knows about the topic or have some resources then please add them in the comments. Also if you know some questions related to this topic, do attach them in the comments.