第三题：爱心蜗牛
本题的主要思路是树形DP，难度中等。
细细读题之后，不难看出，题目中虽然明确的强调了上级和下级的关系，但是由于每个人在一个时间内即可以通知上级也可以通知下级，因此上级和下级实际上是没有区别的。所以我们把这棵树看作一颗无根树。任意选一条鱼作为根节点，构造一个有根树，分析题目的最优性质。
用f[i]表示通知完以i为根的子树所需要的最短时间。以根节点root为例，我们来考虑f[root]的求法。
显然，对于边界值f[leaf]，即叶子节点而言，f[leaf]=1，但是对于非叶节点，问题就稍微复杂了一些。由于开始的时候我们只通知了root，那么root的所有直接儿子只能从root这里得知消息，并且我们假设root所有儿子的f值已经求出。那么root到底先通知那个儿子比较好呢？
假设root的儿子为s1,s2,s3,…sn ，且f[s1]>f[s2]>f[s3]…>f[sn]，则我们让root在每个单位时间内依次通知s1,s2,s3..sn,得到的结果是最优的。也就是f[root]=max{f[si]+i}.也就是说哪个儿子的f值最大我们先通知谁。这个是看起来很显然的结论。但是我们需要证明它。简略证明如下：
假设root的儿子为s1,s2,s3,…sn,且f[s1]>f[s2]>f[s3]…>f[sn].则我们要证明：
f[root]=max{f[si]+i}是最优的。
我们把通知儿子的次序中任意交换两个。即原来有 i<j,且 f[si]>f[sj].，通知这两颗子树的最短时间是 min{f[si]+i,f[sj]+j}；当交换顺序以后，则通知这两个子树的最短时间是Min{f[si]+j,s[sj]+i},因为 f[si]>f[sj] 且 j>i, 则我们交换顺序后的到的最小值显然不会比原来的最优值更优。因此算法得到证明。
由此得到了我们的主算法：枚举每个节点当作树根，建立无根树。每次进行一次树形动态规划，方程为f[i]=max{f[sj]+j}  其中sj是i的儿子。