| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14291 | Run Away!! |
|
Description
Background:
In this peculiar country, every individual's residence is logged in a computerized system. The government, in its whimsical ways, changes everyone's address randomly every day. Resulting in their homes relocating to newly assigned addresses.
You reside in this country, and Kevin used to be your closest friend. However, you've committed the betrayal of stealing Kevin's cherished girlfriend, Tanny. Now, you and Tanny are determined to flee from Kevin's reach. Utilizing your hacking skills, you hack into the government's address system and make sure you and Tanny end up as far away from Kevin as humanly possible! It's like a crazy game of hide-and-seek, but with houses!
Explanation:
In the beginning, you will be given a set of connection of each house (in here houses can be represented as nodes). The connection that will be given is a parent and child in a tree. Each house (node) has distance required to be there and unique address value.
Notes: The connection that will be given will not be always in order from the root, but more likely to be scattered.
Tree example:
Input:
First we assign node 0 as the root with the distance of -30.
Next line, 0 1 7 means 0 is the parent of 1, and 1 has the distance of 7. And 2 4 13 means that 2 is the parent of 4, and 4 has a distance of 13.
Your main aim is to find the maximum distance possible from Node_i to Node_j and print the root of the path that has the maximum distance.
So, in the example above, the maximum distance possible is 34, with the path of: 3 2 4, we then print the root of this subtree which is 2. We do not choose path 1 0 2 4, because the total distance would be only 9, it is less than 34.
There are some operations that Tanny would do in order to stay safe from Kevin.
Operations:
Add A B C
B is representing the new node (house) that Tanny wants to add in the tree (country). A is the parent of B, and C is the distance of node (house) B.
Delete B
After Delete 2:
Check
In this operation you have to give the maximum distance that exist in the tree (country).
And also give the root of the path that gives the maximum distance (house/houses) in the map.
Format of Check:
Input
There will be an integer N in the first line to determine the total nodes (cities) in the tree (country) and integer O that determine the number of operations that would be performed. Initially there will be N+1 nodes (including the root)
The second line would be the value V (index to represent the address) of the root and the distance D that is needed when moving to this root.
The next N line will be value of parent node Pi and the child node Ci, and distance Di of the child node Ci.
The next O line would be operation that Tanny would do to change the nodes (cities) Limit:
0 <= N (Initial Node Excluding Root), V (Value of Node) <= 10000
-1000000 <= D (Node Distance) <= 1000000
1 <= O (Number of Operations) <= 10000
Notes:
The value of node will always be unique for each node, but the distance may not be always unique (different node might have the same distance, but would always differs from each other).
This problem is N-nary tree, meaning 1 node can have more than 2 children.
Guarantee:
The answer would always be unique and exist.
The root will not be deleted in the operation.
There will be only 1 tree, as all of the nodes will be connected in the end although it is scattered at the start.
Output
Print the maximum value and the path as formatted when Check Operation is being called.
After all of the operation is being called, please print the root of the path that gives the maximum distance in the tree.
Format:
Final Root: root_value
Please print newline character after every output.