프로그램 명: boi_ballmachine
제한시간: 1 초
We have a “ball machine” that can be visualized as a rooted tree.
우리는 루트트리를 눈으로 확인할수잇는 볼머신을 가지고있습니다
1. Add k balls to the ball machine: Balls are put one by one into the root node.
2. Remove a ball from a specified node:
입력
The first line contains two integers N and Q - the number of tree nodes and the number of operations.
The next N lines describe the ball machine.
Each of the next Q lines contains two integers and describes an operation to be performed.
An operation of type 1 is denoted by 1 k where k is the number of balls to be added to the machine.
The nodes of the tree are numbered from 1 to N.
루트트리의 노드들은 1부터 n까지의 번호가 매겨져 있습니다.
Each node is either empty or contains one ball. Initially, all nodes are empty.
각 노드들은 비었거나 하나의 볼로 채워져있습니다. 처음에는 모든노드들이 비어있습니다.
While running, the machine can perform operations of two different types:
이 머신이 작동하면, 2가지 다른타입으로 작동하게됩니다.
1. Add k balls to the ball machine: Balls are put one by one into the root node.
1. k개의 볼을 머신에 추가합니다. 각볼들은 하나씩 루트노드에 넣어집니다.
As long as a ball has an empty node directly beneath it, it will roll down.
밑의 노드들이 비어있는만큼 공은 아래로 굴러가게됩니다.
If there are multiple empty child nodes,
이떄 아래의 자식 노드들이 전부다 비어있다면
the ball will choose the one which has the node with the smallest number in its subtree.
볼은 숫자가 작은 노드를 포함하고 노드를 선택하게됩니다.
So if the ball rolls down multiple levels,
그러므로 여러개의 공이 내려간다면,
it makes a choice at each level.
각레벨을 선택하게됩니다.??
For example: If we add two balls to the machine in the picture below,
예를들면 2개의 볼을 그림에보이는 머신에 추가합니다.
they will go to nodes 1 and 3:
그볼들은 1과 3 노드에 들어가게됩니다.
The first ball rolls from node 4 to node 3 because node 3 is empty and it contains node 1 in its subtree (which consists of nodes 3 and 1);
처음의볼은 4에서 3으로 내려갑니다 그이유는 3노드가 비어있고 1노드를 서브트리로 포함하고 있기 때문이지요 (3노드와 1노드를 포함하고있는)
it further rolls from node 3 to node 1. The second ball rolls from node 4 to node 3 as well and stops there.
다음과같이 볼이 노드3에서 노드1로 내려갑니다. 두번째볼은 4에 3노드로 내려가게되고 거기서 몸추게됩니다.
2. Remove a ball from a specified node:
2. 특정한 노드의 볼을 제거합니다
This node becomes empty and balls from above (if there are any) roll down.
선택된 노드는 비워지게됩니다. 그리고 위의 볼이 그자리를 매꾸게됩니다.
Whenever a parent of an empty node contains a ball, this ball will roll down.
어떠한경우든 비워진노드를 포함하고있는 부모노드에 공이있다면 그공은 비워진노드로 굴러가게됩니다.
If we remove balls from nodes 5, 7 and 8 (in this order) from the machine in the picture below, nodes 1, 2 and 3 will become empty.
5,7 8 노드의 볼이 비워진다면 그림과같이 1 2 3 노드의 공들이 그 비워진 자리를 채우고되고 자신들은 비워지게됩니다.
입력
The first line contains two integers N and Q - the number of tree nodes and the number of operations.
첫번쨰 라인은 두개의 정수를 포함하고 있습니다 n, q = 트리노드의 숫자 n , 실행할 숫자 q
The next N lines describe the ball machine.
다음에오는 N라인은 볼머신을 묘사하고있습니다?
Each of these lines contains one integer,
각라인들은 하나의 정수를 포함하고있으며
the number of a node: the i-th of these lines contains the number of node i’s parent node, or 0 if node i is the tree root.
노드의 숫자 : 이 라인은 노드의 넘버를 포함하고있슴니다. 부모노드의, 이것이 0이라면 이것은 트리의 루트입니다??
Each of the next Q lines contains two integers and describes an operation to be performed.
다음 각각의 q라인은 두 작업을 실행할 두개정수의 표현하고잇습니다.
An operation of type 1 is denoted by 1 k where k is the number of balls to be added to the machine.
실행할작업이 1이고 k가 1을 나타낸다면 볼머신에 1의 볼을 추가합니다.
An operation of type 2 is denoted by 2 x where x is the number of the node from which a ball is to be removed.
실행할 작업이 2이고 x가 2를 나타낸다면 x노드의 공은 비워지게 됩니다.
It is guaranteed that all performed operations are correct:
이것은 모든작업에 확실하게 보장됩니다.
Operations will not require to add more balls than there are empty nodes in the ball machine or to remove a ball from an empty node.
빈노드보다 더많은 공이 추가되거나, 빈노드에서 공이제거되는 요구는 없을것입니다.
------------------------------------------------------------------------------
진하게된부분 이해가잘안되.. 도와줘
글쓰기