---
# System prepended metadata

title: 9/20 APCS

---

# 9/20 APCS 
```C++
#include <iostream>
#include <vector>

using namespace std;

vector<int> tree[100005];
bool has_parent[100005]; // initialized with 0 or false
int depth[100005];



int main() {
    int n;
    cin >> n;
    for (int i=1;i<=n;i++) {
        int num_child;
        cin >> num_child;
        for (int j=0;j<num_child;j++) {
            int child; // unknown
            cin >> child;
            tree[i].push_back(child);
            has_parent[child] = true;
        }
    }

    int root;
    for (int i=1;i<=n;i++) {
        if (!has_parent[i]) {
            root = i;
        }
    }

    // dfs

    long long total = 0;
    for (int i=1;i<=n;i++) {
        total += depth[i];
    }
    cout << total << endl;
}
```

### C471
stack = {W, w1, w2, W'} 
w1: n1, w2: n2

w1在上面：
(W+w1) * n2 + W * n1 = W * (n1+n2) + w1 * n2

w2在上面:
(W+w2) * n1 + W * n2 = W * (n1+n2) + w2 * n1

假設w1在上面比較好
<=> w1 * n2 < w2 * n1
<=> w1 / n1 < w2 / n2

wi / ni < wj / nj <=> i就應該放上面

---------------------------

W = total weight = w1 + w2 + X

(W - w1) * n1 < (W - w2) * n2
(w2 + X) * n1 < (w1 + X) * n2
n1 / (w1 + X) < n2 / (w2 + X)

(n_i, w_i)
100個(1,1)
1個(3, 5) -> (3/105)
1個(4, 8) -> (4/108)

我的策略: (4, 8)放最下面

你的策略: (3, 5)放最下面


