记录编号	256418	评测结果	AAAAAAAAAA
题目名称	[CTSC 1997]选课	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.247 s
提交时间	2016-04-30 11:02:59	内存使用	3.24 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

using namespace std;

struct TREE
{
	int father;
	int lch;
	int rch;
	int s;
}t[505];

void Read();
void Work();
void Build();
void Chose(int,int);
void Getroad(int,int);

int m,n;
bool hlch[505];
int f[505][505];
bool first=true;
bool c[505];
int maxl[505][505];
int maxr[505][505];

int main()
{
	freopen("course.in","r",stdin);
	freopen("course.out","w",stdout);
	
	memset(t,0,sizeof(t));
	memset(hlch,false,sizeof(hlch));
	memset(f,0,sizeof(f));
	memset(c,false,sizeof(c));
	
	Read();
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Read()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&t[i].father,&t[i].s);
	}
	
	Build();
}

void Build()
{
	for(int i=1;i<=m;i++)
	{
		int fa=t[i].father;
		if(!hlch[fa])
		{
			t[fa].lch=i;
			hlch[fa]=true;
		}
		else
		{
			int falch=t[fa].lch;
			t[falch].father=i;
			t[i].rch=falch;
			t[fa].lch=i;
		}
	}
}

void Work()
{
	Chose(0,n+1);
	printf("%d\n",f[0][n+1]);
	first=true;
	Getroad(0,n+1);
	for(int i=1;i<=m;i++)
	{
		if(c[i]==true)
		{
			printf("%d\n",i);
		}
	}
}

void Chose(int rt,int num)
{
	if(!first&&(rt==0||num==0||f[rt][num]>0))
	{
		return;
	}
	first=false;
	
	Chose(t[rt].rch,num);//不选rt 
	
	int maxn=0;
	for(int i=0;i<=num-1;i++)//选rt，在其左子树中选i门课 
	{
		Chose(t[rt].lch,i);
		Chose(t[rt].rch,num-1-i);
		
		if(f[t[rt].lch][i]+f[t[rt].rch][num-1-i]+t[rt].s>maxn)
		{
			maxn=f[t[rt].lch][i]+f[t[rt].rch][num-1-i]+t[rt].s;
			maxl[rt][num]=i;
			maxr[rt][num]=num-1-i;
		}
	} 
	
	if(f[t[rt].rch][num]<maxn)
	{
		f[rt][num]=maxn;
	}
	else
	{
		f[rt][num]=f[t[rt].rch][num];
		maxl[rt][num]=0;
		maxr[rt][num]=num;
	}
}

void Getroad(int rt,int num)
{
	if(!first&&(rt==0||num==0))
	{
		return;
	}
	first=false;
	
	if(maxl[rt][num]+maxr[rt][num]==num-1)
	{
		c[rt]=true;
	}	
	Getroad(t[rt].lch,maxl[rt][num]);
	Getroad(t[rt].rch,maxr[rt][num]);
}