1. Abridged Problem Statement

You are given a rooted tree of N programmers (nodes) numbered 1…N, where node 1 is the root (Bill Hates) and each other node’s parent has a smaller number. You want to assign as many \$1000 bonuses as possible under these rules:

- A bonus flows along a parent→child edge.
- Each programmer can either receive a bonus from their parent, or assign a bonus to exactly one child, or do neither—but not both.
- No one can assign more than one bonus downward.

Compute the maximum total bonus amount (1000 × maximum number of receivers) and list the identifiers of all programmers who end up receiving a bonus, in ascending order.

2. Detailed Editorial

A bonus is paid along a chief→subordinate edge, and no programmer can lie on two paid edges (you cannot both receive and give). Hence the chosen bonus edges form a matching in the rooted tree, and we want to maximize the number of matched edges — each matched edge means exactly one new receiver, worth \$1000.

Dynamic programming on trees handles this cleanly. The reference solution keeps two states per node u:

- dp[u][0] = best matching in u’s subtree when u is matched to one of its own children (so u gives a bonus downward).
- dp[u][1] = best matching in u’s subtree when u is left free, available for its parent to match it from above.

Transitions (processing children first, in post-order). Let sum_dp_0 = Σ_{v child of u} dp[v][0].

1. If u is matched to exactly one child v, that child must be in the “free” state dp[v][1] (so u can match it), while every other child stays in dp[·][0]:
     dp[u][0] = max over children v of ( sum_dp_0 − dp[v][0] + dp[v][1] ).

2. The “free” state dp[u][1] either lets u be matched downward (the +1 path, counting u’s child as a receiver) or keeps the best matched value:
     dp[u][1] = max( 1 + sum_dp_0 ,  dp[u][0] ).

Because every parent has a smaller index than each of its children, iterating u from N−1 down to 0 is a valid post-order. The answer for the whole tree is dp[0][0] × 1000 (the root has no parent, so its subtree value is taken from the matched-to-child state).

Reconstruction (finding which nodes receive). We maintain a boolean array take[u], meaning “u is matched up to its parent,” i.e. u receives a bonus. Initialize all false and sweep u in increasing order:

- If take[u] is true but dp[u][1] == dp[u][0], forcing u to receive was unnecessary, so clear take[u].
- If take[u] is true, record u as a receiver and mark every child as take[v] = false (they cannot receive, since u is already receiving and cannot also give).
- Otherwise (u is free to give), look for the child v achieving dp[u][0] == sum_dp_0 − dp[v][0] + dp[v][1]; set take[v] = true and leave the other children false.

Every u with take[u] true is a receiver. They are encountered in ascending order, so the output list is already sorted.

Time complexity is O(N). Memory is O(N).

3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<vector<int>> adj;

void read() {
    cin >> n;
    adj.assign(n, {});
    for(int i = 1; i < n; i++) {
        int p;
        cin >> p;
        adj[p - 1].push_back(i);
    }
}

void solve() {
    // - A grant is paid along a chief->subordinate edge, and no programmer is on
    //   two paid edges, so the set of grants is a matching in the hierarchy
    //   tree. We maximize the number of matched edges (each worth 1000).
    //
    // - Tree DP with two states per node u: dp[u][0] is the best matching in
    //   u's subtree when u is matched to one of its children, dp[u][1] is the
    //   best when u is left free for its own parent to match it. With sum_dp_0 =
    //   sum of dp[child][0], matching u to child v gives sum_dp_0 - dp[v][0] +
    //   dp[v][1]; dp[u][1] additionally counts the case where u is matched
    //   downward (the +1 path) versus left free, taking the max. Children have
    //   larger ids than their chief, so a reverse-id sweep is post-order.
    //
    // - Reconstruction sweeps ids in increasing order. take[u] records whether
    //   u is matched up to its parent; if so it cannot also match down, so we
    //   pick the child v achieving dp[u][0] = sum_dp_0 - dp[v][0] + dp[v][1],
    //   record v as taken (it receives the grant), and free the rest.

    vector<vector<int>> dp(n, vector<int>(2, 0));
    for(int u = n - 1; u >= 0; u--) {
        dp[u][1] = 1;
        for(int v: adj[u]) {
            dp[u][1] += dp[v][0];
        }

        int sum_dp_0 = 0;
        for(int v: adj[u]) {
            sum_dp_0 += dp[v][0];
        }

        for(int v: adj[u]) {
            dp[u][0] = max(dp[u][0], sum_dp_0 - dp[v][0] + dp[v][1]);
        }
        dp[u][1] = max(dp[u][0], dp[u][1]);
    }

    vector<int> ans;
    vector<bool> take(n, false);
    for(int u = 0; u < n; u++) {
        if(take[u] && dp[u][1] == dp[u][0]) {
            take[u] = false;
        }

        if(take[u]) {
            ans.push_back(u + 1);
            for(int v: adj[u]) {
                take[v] = false;
            }
        } else {
            int sum_dp_0 = 0;
            for(int v: adj[u]) {
                sum_dp_0 += dp[v][0];
            }

            int take_child = -1;
            for(int v: adj[u]) {
                if(dp[u][0] == sum_dp_0 - dp[v][0] + dp[v][1]) {
                    take_child = v;
                    take[v] = true;
                    break;
                }
            }

            for(int v: adj[u]) {
                if(v != take_child) {
                    take[v] = false;
                }
            }
        }
    }

    cout << dp[0][0] * 1000 << '\n';
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution with Detailed Comments

This Python version uses the equivalent formulation dp0[u] = best if u is free (not receiving from its parent) and dp1[u] = best if u receives from its parent; the answer is dp0[0] × 1000.

```python
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
    n = int(input())
    # Build adjacency list; 0-based indexing
    children = [[] for _ in range(n)]
    parents = list(map(int, input().split()))
    for i, p in enumerate(parents, start=1):
        children[p-1].append(i)

    # dp0[u], dp1[u] as in the editorial
    dp0 = [0]*n
    dp1 = [0]*n

    # Post-order: since children always have larger index, loop u = n-1..0
    for u in range(n-1, -1, -1):
        # Case: u receives from its parent
        dp1[u] = 1 + sum(dp0[v] for v in children[u])

        # Sum of dp0 over all children
        sum0 = sum(dp0[v] for v in children[u])
        # If u matches no child
        best = sum0
        # If u matches exactly one child v
        for v in children[u]:
            cand = sum0 - dp0[v] + dp1[v]
            if cand > best:
                best = cand
        dp0[u] = best
        # Possibly treat u as a receiver if that’s equally good
        if dp1[u] < dp0[u]:
            dp1[u] = dp0[u]

    # Reconstruction of receivers
    take = [False]*n
    receivers = []
    for u in range(n):
        # If we previously marked take[u] but it wasn't needed, clear it
        if take[u] and dp1[u] == dp0[u]:
            take[u] = False

        if take[u]:
            # u receives
            receivers.append(u+1)   # store 1-based
            # its children cannot receive
            for v in children[u]:
                take[v] = False
        else:
            # u is free: find if u matched one child
            sum0 = sum(dp0[v] for v in children[u])
            picked = None
            for v in children[u]:
                if dp0[u] == sum0 - dp0[v] + dp1[v]:
                    picked = v
                    take[v] = True
                    break
            # all other children do not receive
            for v in children[u]:
                if v != picked:
                    take[v] = False

    # Output total money and sorted receivers
    total_money = dp0[0] * 1000
    print(total_money)
    print(*receivers)

if __name__ == "__main__":
    main()
```

5. Compressed Editorial

- Represent the hierarchy as a rooted tree (root = node 1); chosen bonus edges form a matching.
- Keep two states per node u: dp[u][0] = best matching when u is matched to a child, dp[u][1] = best when u is left free for its parent.
- With sum_dp_0 = Σ dp[child][0]: dp[u][0] = max over child v of (sum_dp_0 − dp[v][0] + dp[v][1]); dp[u][1] = max(1 + sum_dp_0, dp[u][0]).
- Process nodes in decreasing index (post-order); answer = dp[0][0] × 1000.
- Reconstruct by sweeping ascending, tracking take[u] (whether u receives) and choosing, at each free node, the child v that achieves dp[u][0].
