11987 - Almost Union-Find

Difficulty : medium

Solution Description :

Union-Find problem

You can solve this problem using Union-Find algorithm with some extra work for command 2.

You can use three array set[] for union find, Element[] for number of element in parent and Sum[] for sum of element in parent.

For n=5 at first set value to three arrays.
1= set:-1 Element:1 Sum:1
2= set:-1 Element:1 Sum:2
3= set:-1 Element:1 Sum:3
4= set:-1 Element:1 Sum:4
5= set:-1 Element:1 Sum:5
Here set[i]=-1 indicate parent node.

For command: 1 1 2 (Simple Union-Find)
1= set: 2 Element:0 Sum:0 (1 is child of 2)
2= set:-1 Element:2 Sum:3 (2 is a parent of 1) Sum[2] = Sum[2]+Sum[1]
3= set:-1 Element:1 Sum:3
4= set:-1 Element:1 Sum:4
5= set:-1 Element:1 Sum:5

For command: 2 3 4 (Move command)
In previous stage 3 is a parent node and have 1 element so, you can use simple Union-Find
1= set: 2 Element:0 Sum:0
2= set:-1 Element:2 Sum:3
3= set: 4 Element:0 Sum:0
4= set:-1 Element:2 Sum:7
5= set:-1 Element:1 Sum:5
 
For command: 1 3 5 (Simple Union-Find)
1= set:2 Element:0 Sum:0
2= set:-1 Element:2 Sum:3
3= set:4 Element:0 Sum:0
4= set:5 Element:0 Sum:0
5= set:-1 Element:3 Sum:12

For command: 2 4 1 (Move command)
1= set: 2 Element:0 Sum:0
2= set:-1 Element:3 Sum:7
3= set: 5 Element:0 Sum:0 
(This is the extra work, 4 move to new group, but in old group 4 is the parent of 3. So, you need to change all the value of set[] if set[i]==4 by group leader (Here group leader 5) of old group then move the element 4 to new group)
4= set: 2 Element:0 Sum:0
5= set:-1 Element:2 Sum:8

For command: 2 5 4 (Move command)
1= set: 2 Element:0 Sum:0
2= set:-1 Element:4 Sum:12
3= set:-1 Element:1 Sum:3 (New group leader)
4= set: 2 Element:0 Sum:0
5= set: 2 Element:0 Sum:0
(There is another extra work, 5 move to new group, but in old group 5 is the group leader. First you need to find new group leader in old group. Then you need to change all the value of set[] if set[i]==5 by the new group leader (Here new group leader 3) of old group then move the element 4 to new group).