<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

195. New Year Bonus Grant
time limit per test: 0.75 sec.
memory limit per test: 65536 KB
input: standard
output: standard



All programmers of Mocrosoft software company are organized in a strict subordination hierarchy. Every programmer has exactly one chief, except Bill Hates who is also the head of the company and has no chief.

Due to the celebration of the new 2003 year, chief accountant of Mocrosoft decided to pay a New Year Bonus Grant of 1000 dollars to some programmers. However being extremely concerned of the company wealth she would like to designate the least possible amount of money for these grants. On the other hand she didn't want to be accused of being too greedy or of giving preferences to some programmers. To do this, she developed the following scheme of grants appointment:


Each programmer may either assign a grant to one of his subordinates or have a grant assigned to him by his chief or none of the above.
No programmer can simultaneously receive a grant and assign a grant to one of his subordinates.
No programmer can assign a grant to more than one of his subordinates


The scheme seemed to be designed perfectly — nobody would like to assign a grant to anybody since in this case he himself would not receive money. But programmers somehow discovered the plan of chief accountant and decided to make a trick to get the most money possible and share them fairly afterwards. The idea was to make such grant assignments that the total amount of grant money received is maximum possible.

You were selected to write the program which will find the optimal grants appointment.

Input

The first line of the input file contains integer N — the number of programmers in Mocrosoft company (2 ≤ N ≤ 500 000). Each programmer is assigned his unique identifier — integer number ranging from 1 to N. Bill Hates has number 1 and each programmer has the number greater then the number of his chief. The second line of the input file contains N-1 integers, i-th of which being the number of the chief of the worker whose number is (i + 1).

Output

On the first line of the output file print the maximum possible amount of money workers can get. On the second line output the numbers of programmers that will receive grant in ascending order.

Sample test(s)

Input
4
1 1 2

Output
2000
3 4

Author:	Andrew Stankevich
Resource:	Petrozavodsk Winter Trainings 2003
Date:	2003-02-06

<|response|>
1. Abridged Problem Statement
You are given a rooted tree of N programmers (nodes) numbered 1…N, with node 1 as the root (“Bill Hates”). Every other node has exactly one parent whose number is smaller. We want to select a set of “bonus assignments” along parent→child edges so as to maximize the number of children who actually receive a \$1000 bonus, under these constraints:
  - A node can either receive a bonus from its parent, or assign a bonus to exactly one of its children, or do neither—but not both.
  - No node can assign more than one bonus downward.

Output the maximum total bonus (in dollars) and the list of all nodes who receive a bonus, in ascending order.

2. Key Observations
1. A bonus is paid along a parent→child edge, and no node can lie on two paid edges, so the chosen bonus edges form a matching in the rooted tree. Maximizing money = maximizing the number of matched edges (each worth \$1000).
2. We solve it by a tree-DP with two states per node u (as in the reference C++):
   - dp[u][0]: best matching in u’s subtree when u is matched to one of its own children (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.
3. Recurrence (after computing all children). Let sum_dp_0 = Σ_{v child of u} dp[v][0]:
   - dp[u][0] = max over children v of ( sum_dp_0 − dp[v][0] + dp[v][1] )  (match u to one child v).
   - dp[u][1] = max( 1 + sum_dp_0 ,  dp[u][0] )  (either match u downward, counting its child, or keep the matched value).
4. The answer is dp[0][0] × 1000.
5. To reconstruct which nodes receive, do a second sweep in increasing index order, keeping a boolean array take[u] meaning “u receives from its parent,” resolving at each free node which child it matched.

3. Full Solution Approach
Step 1. Read N and the parent array. Build a 0-based adjacency list of children for each node.
Step 2. Allocate dp[u][0], dp[u][1] for all u.
Step 3. Post-order DP: because every parent has a smaller index, process u from N−1 down to 0.
  - Compute dp[u][1] = 1 + sum of dp[v][0] over all children v.
  - Compute sum_dp_0 = sum of dp[v][0] over all children v.
  - Compute dp[u][0] = max over children v of ( sum_dp_0 − dp[v][0] + dp[v][1] ).
  - Set dp[u][1] = max(dp[u][0], dp[u][1]).
Step 4. Reconstruction of the matching:
  - Initialize take[u]=false for all u, and an empty vector `receivers`.
  - Sweep u from 0 to N−1:
     a) If take[u] is true but dp[u][1]==dp[u][0], cancel it (take[u]=false).
     b) If take[u] is still true, record u+1 in `receivers` and set take[v]=false for all children v.
     c) If take[u] is false, compute sum_dp_0 = Σ dp[v][0] and find a child v with dp[u][0] == sum_dp_0 − dp[v][0] + dp[v][1]; set take[v]=true, leave the rest false.
  - Nodes with take[u]==true are the receivers, encountered in ascending order.
Step 5. Output dp[0][0] × 1000 and the list `receivers`.

4. C++ Implementation
```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;
}
```

5. Python Implementation 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())
    parents = list(map(int, input().split()))
    # Build children lists, 0-based
    children = [[] for _ in range(n)]
    for i, p in enumerate(parents, start=1):
        children[p-1].append(i)

    # dp0[u], dp1[u] as described above
    dp0 = [0]*n
    dp1 = [0]*n

    # Post-order: since parent < child, loop from n-1 down to 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])

        # Case: u is free
        sum0 = sum(dp0[v] for v in children[u])
        best0 = sum0
        for v in children[u]:
            candidate = sum0 - dp0[v] + dp1[v]
            if candidate > best0:
                best0 = candidate
        dp0[u] = best0

        # Ensure dp1[u] >= dp0[u] for reconstruction logic
        if dp1[u] < dp0[u]:
            dp1[u] = dp0[u]

    # Reconstruct which nodes receive
    take = [False]*n  # take[u]=True means u receives from its parent
    receivers = []

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

        if take[u]:
            # u is a receiver
            receivers.append(u+1)  # convert to 1-based
            # Children cannot receive
            for v in children[u]:
                take[v] = False
        else:
            # u is free: detect if it matched a child
            sum0 = sum(dp0[v] for v in children[u])
            picked = None
            if dp0[u] > sum0:
                for v in children[u]:
                    if dp0[u] == sum0 - dp0[v] + dp1[v]:
                        picked = v
                        take[v] = True
                        break
            # all other children are not receiving
            for v in children[u]:
                if v != picked:
                    take[v] = False

    # Output
    print(dp0[0] * 1000)
    print(*receivers)

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