Help needed for an interesting oa problem!
Difference between en3 and en4, changed 358 character(s)
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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English codehacker4689_p 2023-09-30 11:01:33 2 Tiny change: '_nodes ≤ 105\n\n• 1 ≤' -> '_nodes ≤ 1e5\n\n• 1 ≤'
en4 English codehacker4689_p 2023-09-30 09:23:27 358
en3 English codehacker4689_p 2023-09-30 09:02:39 22 Tiny change: ' values.\nSeen th' -> ' values.\nConstraints: n<=1e5.\nSeen th'
en2 English codehacker4689_p 2023-09-30 08:13:43 57
en1 English codehacker4689_p 2023-09-30 06:31:29 576 Initial revision (published)