
In the Kingdom of Arborvale, there is a hierarchical system of nobles arranged in a tree-like structure. The kingdom has 'n' nobles, each assigned a unique number from 1 to 'n'. At the top is the King, who is the root of the structure.
Each noble has a parent, except for the King. Some nobles are loyal and respect their ancestors, while others are rebellious.
You are tasked with restoring peace by removing rebellious nobles according to a specific process:
1)You must select a noble to remove who meets all of the following criteria:
I) Is not the King (i.e., is not the root).
II) Is rebellious (does not respect their parent).
III) Has no children who are loyal (i.e., all of its children are also rebellious, or it has no children at all).
2)If multiple nobles meet these criteria, you must select the one with the smallest number.
3)When a noble is removed, all of its children are immediately re-assigned to its parent. This does not affect any other nobles in the current step but may influence future removals.
4)The process continues, selecting and removing one noble at a time, until no nobles are left that meet the removal criteria.
Your task is to determine the order in which the rebellious nobles will be removed.
The first line contains an integer 'n', the number of nobles.
The next 'n' lines describe the nobles from 1 to 'n'. The i-th line (for noble i) contains two integers, p_i and c_i:
I) p_i: The parent of noble i. The King's parent is -1.
II) c_i: The status of noble i. c_i = 1 if the noble is loyal (respects its parent), and c_i = 0 if the noble is rebellious.
Print a single line containing the space-separated numbers of the nobles in the order they are removed.
If no nobles can be removed, print the word "Peaceful".
The problem uses 1-based indexing for nobles (from 1 to 'n').
The re-parenting of children after a removal does not happen in the current implementation, as it has been determined that the set of removable nobles is static based on the problem's rules. A noble's condition for removal depends on its own children's loyalty, which does not change throughout the process.
7
-1 1
1 1
1 0
2 1
2 0
3 0
5 0
3 5
The hierarchy is as follows:
- King 1 has children 2 and 3.
- Noble 2 has children 4 and 5.
- Noble 3 has child 6.
- Noble 5 has child 7.
Let's check the nobles who are rebellious (c=0): 3, 5, 6, 7.
Noble 3: Rebellious. Its only child is 6, who is also rebellious. So, 3 has no loyal children. It is a candidate for removal.
Noble 5: Rebellious. Its only child is 7, who is also rebellious. It is a candidate for removal.
Noble 6: Rebellious. It has no children. It is a candidate for removal.
Noble 7: Rebellious. It has no children. It is a candidate for removal.
5
-1 1
1 0
2 1
1 0
4 1
Peaceful
The rebellious nobles are 2 and 4.
Noble 2: Rebellious. However, its child, noble 3, is loyal (c=1). Therefore, noble 2 cannot be removed.
Noble 4: Rebellious. However, its child, noble 5, is loyal (c=1). Therefore, noble 4 cannot be removed.
Since no nobles meet all the criteria, the kingdom is considered "Peaceful".
The expected time complexity is O(N log N) due to sorting the candidates.
1 <= n <= 100,000
p_i is -1 or between 1 and n.
c_i is 0 or 1.
The input will always describe a valid tree structure with a single root.
Time limit: 1sec
The expected time complexity is O(N log N) due to sorting the candidates.