学步园

An Old Stone Game

这道题看了好几遍，又看了看别人给的数据才看明白。意思就是现在有一棵树，有一些石头，依次把石头放在树叶上，如果一个节点的叶子节点全有一个石头了，就可以把它们的石头去掉，并把其中的一个石头放在这个节点上，而这个结点就相当于一个叶子节点了，去掉的石头可以再用，问直到根节点上放了石头，一共要多少石头。

对树的存法不太清楚，怎么做也没明白。上网找到一篇解题报告
，看了一会明白了。

其实不是很难。想算一个节点所需要
的石头（为了避免麻烦，就从根结点开始），如果没有子结点了，那只需要一个石头就够了，如果有，就分别算出每个子节点所要的石头，然后就是最重要的步骤。

把它们从大到小排序，a1 - an，现在想如果a1 > a2 > ... > an的话，处理完1要用去a1个石头，留下了一个剩a1-1个，而a1 > a2，所以a1-1 >= a2，所以2就不用额外的石头了，同理到an也不再需要额外的石头。

那什么情况需要呢，例如 a1 = 4, a2 = 4, a3 = 3，那1剩下的石头不够2用，就要再加一个，也就是i需要ai再加上前边放好的石头，当然放石头什么顺序都行，而且结果是一样的，就可以从大到小排序，从大到小放，i就需要ai+i-1个，最大

需求

的就是父节点的需求。

下面是自己写的代码，没有什么难理解的地方：

#include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <cstdlib><br /> #include <algorithm><br /> #include <string><br /> #include <cstdio><br /> #include <climits><br /> #include <queue><br /> using namespace std;<br /> int tree[202][202];<br /> int solve(int x)<br /> {<br /> if (tree[x][0] == 0)<br /> return 1;<br /> int tmp[201];<br /> for (int i=1; i <= tree[x][0]; i++)<br /> tmp[i-1] = solve(tree[x][i]);<br /> sort(tmp, tmp+tree[x][0]);<br /> for (int i=0; i < tree[x][0]; i++)<br /> tmp[i] += tree[x][0] - i - 1;<br /> return *max_element(tmp, tmp + tree[x][0]);<br /> }<br /> int main()<br /> {<br /> int M;<br /> scanf("%d", &M);<br /> while (M--)<br /> {<br /> memset(tree, 0, sizeof(tree));<br /> int N;<br /> scanf("%d", &N);<br /> for (int i=1; i <= N; i++)<br /> {<br /> scanf("%*d%d", tree[i]+0);<br /> for (int j=1; j <= tree[i][0]; j++)<br /> scanf("%d", tree[i]+j);<br /> }<br /> printf("%d/n", solve(1));<br /> }<br /> return 0;<br /> }