在動物王國中，為了建立良好的傳遞網路，每個動物都會有左右需要傳東西的人，我們稱之為「左節點」和「右節點」。
其中根節點為動物王國的國王，即動物0。當動物i 拿到 K 個東西後，會將所拿到的東西以 (自己 + 子節點數量) 做均分，均分完的等份，分別傳遞給其左節點、右節點和自己做保留；若無法均分時，則會將剩下的個數優先保留給自己。
其子節點則繼續這個過程，直到沒有任何子節點為止。
以上圖為例，假設動物0 拿到 9 個東西，則會其均分為三等份後，將其中 3 個傳給左邊的動物1（如紅字所示），另外 3 個傳給右邊的動物2，剩下 3 個則自己保留（螢光黃所示）。
依序同理，最後每個動物所能夠得到的物品數量如螢光黃所示。
現在已知有 N 個動物，以及動物間的左右節點關係，假設動物國的國王動物0 得到了 K 個杯子蛋糕，請問依照上述傳遞規則，每個動物最後分別可以得到幾個杯子蛋糕？
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有兩個正整數 N 和 K，代表總共有 N 個動物 (1 ≤ N ≤ 10)，動物編號依序為 0、1、…、N-1，並且有 K 個杯子蛋糕要由動物0 開始往下傳送。 接著依序有 N 行，每行有三個整數 a (0 ≤ a ≤ N-1)、L 和 R (-1 ≤ L、R ≤ N-1)，代表動物a 的左子節點為 L，右子節點為 R，如果沒有該子節點，則以 -1 表示；並且動物0 必定為根節點。 | 由左至右，分別印出 動物0、動物1、…、動物N-1，最後可得的杯子蛋糕數量。 |
| 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 |
解題思路
可以宣告一個 map<int, pair<int, int>> MAP 來紀錄每一個節點的左右節點是什麼，並且宣告一個 map<int, int>ans 來存答案。
跑一個 DFS，需要的參數是目前要分的蛋糕數量 cake 和目前的節點位置 pos。預設一個變數 split 為 1，代表需要分蛋糕給多少人，如果 MAP[pos].first != -1，代表左邊有人，所以 split++，同樣如果 MAP[pos].second != -1 就代表右邊有人，所以一樣要 split++。如果 split == 1 ，代表已經不會繼續往下走了，將 ans[pos] 設為 cake 並且 return。
如果 DFS 要繼續往下走，則宣告一個變數 divide 為 cake/split，並且先將 ans[pos] 設為 divide。如果 cake % split != 0，則要將多餘的分給目前位置，所以要 ans[pos] += cake % split。
如果目前位置左邊有節點的話就呼叫 DFS，只是蛋糕數量變成 divide，並且目前位置變成 MAP[pos].first，相同道理也用在右邊。
最後跑一個 For迴圈，從 1 到 N-1，將 ans 中的資料輸出。
範例程式碼－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