记录编号	45262	评测结果	AAAAAAAAAA
题目名称	[CTSC 1997]选课	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	2.768 s
提交时间	2012-10-23 07:41:57	内存使用	65.00 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int val[10010],sonnum[10010],f[10010][510];
bool used[10010];
vector<int> son[10010],rec[10010][510];

void fillit(int pos,int limit)
{
    int i,j,k,temp;
	for (j=limit-1;j>=0;j--)
		for (i=0;i<sonnum[pos];i++)
			rec[pos][j].push_back(0);
    for (i=0;i<sonnum[pos];i++)
    {
        fillit(son[pos][i],limit-1);
        for (j=limit-1;j>=1;j--)
        {
            for (k=0;k<=j;k++)/*1*//* "1" --> "0" */
            {
				temp=f[pos][j-k]+f[son[pos][i]][k];
                if (f[pos][j]<=temp)/*2*//* "<" --> "<=" */
				{/* put 1 and 2 together : didn't consider the situation of inherition(继承) */
					f[pos][j]=temp;
					rec[pos][j][i]=j-k;
				}
            }
        }
    }
    for (i=limit;i>=1;i--)
        f[pos][i]=f[pos][i-1]+val[pos];
}

void findway(int pos,int limit)
{
	used[pos]=true;
	int poi,deep;
	poi=limit-1;
	deep=sonnum[pos]-1;
	while (deep>=0&&limit>0)
	{
		if (poi!=rec[pos][poi][deep])
			findway(son[pos][deep],poi-rec[pos][poi][deep]);
		poi=rec[pos][poi][deep];
		deep--;
	}
}

int main(void)
{
    freopen("course.in","r",stdin);
    freopen("course.out","w",stdout);
    int i,n,lim,temp;
    cin>>n>>lim;
	lim++;
    val[0]=0;
    for (i=1;i<=n;i++)
    {
        cin>>temp>>val[i];
        sonnum[temp]++;
        son[temp].push_back(i);
    }
    fillit(0,lim);
    cout<<f[0][lim]<<endl;
	findway(0,lim);
	for (i=1;i<=n;i++)
		if (used[i])
			cout<<i<<endl;
    return(0);
}