In the animal kingdom, to establish a good communication network, each animal has individuals on the left and right to whom they need to pass things. We call these individuals the "left node" and the "right node."
In the animal kingdom, the root node is the king, which is animal0. When animali receives K items, it will divide the items evenly by (itself + the number of child nodes). The evenly divided parts are then distributed to the left node, and right node, and kept for itself. If it cannot be divided evenly, the remaining items are prioritized to be kept by itself.
Its child nodes will continue this process until there are no more child nodes left.
For example, if animal0 receives 9 items, it will evenly divide them into three parts, then distribute 3 items to the left animal1 (as shown in red), 3 items to the right animal2, and keep the remaining 3 items for itself (highlighted in yellow).
Each animal will follow the same process, and the final number of items each animal can obtain is highlighted in yellow.
There are N animals and the relationships between the animals in terms of their left and right nodes are known. If the king of the animal kingdom, animal0, receives K cupcakes, how many cupcakes will each animal receive in the end according to the given distribution rules?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two positive integers N and K, representing there are N animals (1 ≤ N ≤ 10), with animal IDs ranging from 0 to N-1, and K cupcakes that will start being passed down from animal0.
Following this, there are N lines, each containing three integers a (0 ≤ a ≤ N-1), L, and R (-1 ≤ L, R ≤ N-1), representing that animala has left child L and right child R. If a child does not exist, it is represented by -1. Animal0 is always the root node. | From left to right, print the number of cupcakes each animal (animal0, animal1, ..., animalN-1) finally receives. |
| 6 9 0 1 2 1 3 4 2 5 -1 3 -1 -1 4 -1 -1 5 -1 -1 | 3 1 2 1 1 1 |
Thought Process
Declare a map<int, pair> MAP to store the left and right nodes for each node, and a map ans to store the answers.
Run a DFS where the parameters are the current number of cupcakes to distribute "cake" and the current node position "pos." Initialize a variable split to 1, indicating how many recipients there are. If MAP[pos].first != -1, indicating there is a left node, increment split++. Similarly, if MAP[pos].second != -1, indicating there is a right node, increment split++. If split == 1, it means there are no more nodes to distribute to, set ans[pos] to cake, and return.
If the DFS continues further down, declare a variable "divide" as cake/split, and set ans[pos] to divide initially. If cake % split != 0, distribute the remainder to the current position, so ans[pos] += cake % split.
If there is a node on the left side of the current position, call DFS with the cupcake quantity as divide, and the current position as MAP[pos].first. Similarly, apply the same logic for the right side.
Finally, run a for loop from 1 to N-1 and print the data from ans.
Sample Code－ZeroJudge G309: Cupcake
#include <iostream>
#include <map>
using namespace std;
map<int, pair<int, int>>MAP;
map<int, int>ans;
void DFS(const int cake, const int pos) {
int split = 1;
if (MAP[pos].first != -1) split++;
if (MAP[pos].second != -1) split++;
if (split == 1) {
ans[pos] = cake;
return;
}
const int divide = cake/split;
ans[pos] = divide;
if (cake % split != 0) ans[pos] += cake % split;
if (MAP[pos].first != -1) DFS(divide, MAP[pos].first);
if (MAP[pos].second != -1) DFS(divide, MAP[pos].second);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
for (int i = 0; i<N; i++) {
int a, l ,r;
cin >> a >> l >> r;
pair<int, int>tmp;
tmp.first = l;
tmp.second = r;
MAP[a] = tmp;
}
DFS(K, 0);
for (int i = 0; i<N; i++) cout << ans[i] << " ";
cout << "\n";
}
//ZeroJudge G309
//Dr. SeanXD