There is an undirected tree T of size n, with edges of length 1. Initially, each of the nodes(1-indexed) 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.↵
Constraints: n<=1e5.↵
↵
Example↵
↵
T_nodes = 4↵
↵
T_from= [1, 2, 3]↵
↵
T_to= [2, 3, 4]↵
↵
↵
In the minimum distance shuffle, node values are switched with their neighbours. The distance is 1 +1+1+1=4. In the maximum distance shuffle, the distance is 3+1+1+3=8. Return [3, 8].↵
↵
Constraints↵
↵
• 1 ≤ T_nodes ≤ 105↵
↵
• 1 ≤ T_from[i], T_to[i] ≤ T_nodes↵
↵
• T_from[i] ≠ T_to[i]↵
↵
↵
Seen this in some recent oa and tried alot but not able to solve. Can anyone help please?
↵
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.↵
↵
Example↵
↵
T_nodes = 4↵
↵
T_from= [1, 2, 3]↵
↵
T_to= [2, 3, 4]↵
↵
↵
In the minimum distance shuffle, node values are switched with their neighbours. The distance is 1 +1+1+1=4. In the maximum distance shuffle, the distance is 3+1+1+3=8. Return [3, 8].↵
↵
Constraints↵
↵
• 1 ≤ T_nodes ≤ 105↵
↵
• 1 ≤ T_from[i], T_to[i] ≤ T_nodes↵
↵
• T_from[i] ≠ T_to[i]↵
↵
↵
Seen this in some recent oa and tried alot but not able to solve. Can anyone help please?