1694 An Old Stone Game

問題概要

ノード数200以下の木を使った次のようなゲームがある。

• 最初にK個の石をかごに入れる。
• かごの石は好きな葉に置くことができる。
• 子全てに石のおかれたノードがあるとき、子の全ての石をかごに戻し、そのノードに石を置くことができる。
• 根に石が置かれると勝ちである。

木が与えられたとき、最初にかごに入れる石の数Kのゲームクリアに必要な最小値を求めよ。

解法

あるノードに石を置くのに必要なコストは次のような考え方をすればよい。

子1,2,...にそれぞれ石を置くのに必要なコストをa[i]とすると、a[i]の大きい順に石を置いていくのが最適。
子のi個まで石を置き終えたあとで、i+1番目の子に石を置くのに必要なコストはi+a[i+1].
よってそのノードに置く石の数は、これらの最大値となる。

ソースコード

int n;
vector<vi> e;

int rec(int c)
{
	if(e[c].empty())return 1;
	
	int m=0,a[200];
	fr(i,e[c])a[m++]=rec(*i);
	sort(a,a+m,greater<int>()); rep(i,m)a[i]+=i;
	sort(a,a+m,greater<int>());
	return a[0];
}

int main()
{
	int cs; scanf("%d",&cs);
	rep(CS,cs)
	{
		scanf("%d",&n); e.clear(); e.resize(n);
		rep(i,n)
		{
			int a,b,c; scanf("%d%d",&a,&b);
			rep(j,b)scanf("%d",&c),e[a-1].pb(c-1);
		}
		printf("%d\n",rec(0));
	}
	return 0;
}