题目来源：

https://vjudge.net/contest/293466#problem/G

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2315

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.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

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 Input

1
4
1 1 2

Sample Output

2000
3 4

题意：

微软公司要发奖金，有很多份1000的奖金，求得是最大能从财务部那里获得多少奖金以及获得奖金的结点。。。。题意贼难懂

样例解释：

4（4个人）

1 1 2（第2个人的上司是1，第三个人的上司是1，第四个人的上司是2）

题目对于发奖金有三个规定：

1.每个人可以给自己的下属发奖金，可以等老板给自己发奖金，可以什么都不做

2.每个员工要么拿上司的钱要么给自己的下属分钱，两个只能选择一样

3.如果一个员工有很多下属，那么他只能给自己的其中一个下属分钱

思路：

贪心，用一个数组标记某个人有没有人分到钱，然后从后面扫描一遍，当这个人以及这个人的上司都没有分到钱的时候，就把钱给这个人，存在一个数组里，然后输出.（详细见代码注释）

参考代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
#define lson l,m,root<<1
#define ll long long
#define rson m+1,r,root<<1|1
using namespace std;
const int N=5e5+5;
ll vis[N];//标记有没有分到钱
ll a[N];//记录每个人的上司
ll ans[N];//记录谁拿了钱
int main()
{
    ll t,n,x;
    scanf("%lld",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        memset(ans,0,sizeof(ans));
        ll len=0;
        scanf("%lld",&n);
        for(ll i=2; i<=n; i++)
            scanf("%lld",&a[i]);
        for(ll i=n; i>=2; i--)
        {
            ll f=a[i];//这个人的上司
            if(vis[i]==0&&vis[f]==0)//当且仅当这个人得到钱和它的上司也没得到钱并且和他同一个上级的人都没得到钱（都用vis标记）
            {
                ans[len++]=i;//给这个人发钱
                vis[i]=1;
                vis[f]=1;//标记一下这个人和它的上司
            }
        }
        printf("%lld\n",len*1000);//输出获得的钱数
        sort(ans,ans+len);//进行升序排序，题目要求
        for(ll i=0; i<len-1; i++)
            printf("%lld ",ans[i]);
        printf("%lld\n",ans[len-1]);//控制格式
        if(t^1)printf("\n");
    }
    return 0;
}