杭电OJ的hdu3290题目魔法苹果树的解题思路是什么？

本文共计953个文字，预计阅读时间需要4分钟。

题目大意：给出一个有N个节点的树，要求：

1.计算每个叶子节点的label对应的苹果数量，等于叶子节点的数量。

2.对于某个节点，如果它有K个子节点，并且它的K个子节点都生出了苹果，那么这个节点才开始生长苹果。

题目大意：给出一个有N(0

题目大意：给出一个有N(0

1.叶子节点生长出的苹果数量等于叶子节点的label。

2.某父亲节点有K个儿子节点，直到它的K个儿子节点都生长出苹果，父亲节点才开始生长苹果。父亲节点长出的苹果数量等于它的  所有儿子中苹果数量第(k+1)/2小的  儿子节点的苹果数量。

求根节点生长出的苹果数量。

举个栗子：如下图所示，label为4,5,6,7的节点是叶节点，根据规则一，叶节点生长的苹果数量为他们的编号，那么他们生长出的苹果数量分别为4,5,6,7个。接下来，节点2,3的所有子节点有已经生长出苹果了，根据规则二，轮到节点2,3生长苹果了。节点2有2个子节点，根据计算：(2+1)/2 = 1，节点2的苹果数量等于它的所有儿子节点苹果数量中第1小的儿子节点苹果数量，也就是等于节点4的苹果数量。同样的，节点3的苹果数量为6。最后计算节点1的苹果数量即可。

1、用邻接表来存储这颗树。

2、用visit数组记录每个节点的入度，也就是方面后面找到根节点，根节点的入度为0。

3、根据题目规则，设计DFS搜索来求每个节点的苹果数量。