桃花

[编程题]桃花

热度指数：3 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

桃花一簇开无主，可爱深红映浅红。

——《题百叶桃花》

桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。

输入描述:

第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数a_i,b_i ，表示桃树上的节点a_i,b_i之间有一条边。

输出描述:

第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。

示例1

输入

3
1 2
2 3

输出

示例2

输入

3
1 2
1 3

输出

示例3

输入

输出

备注:

对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

算法知识视频讲解

Java

牛客203596504号

一条链上的桃花，如果我们考虑其中最低的一朵，必然构成V字形。
(如果最低的一朵在顶端，就是直链。那它必然是唯一的分枝，否则就有更长的链)
那么，从最低一朵向上看，V字的两侧分别是最高子树高度(max1)和次高子树高度(max2)。
所以，我们只需DFS遍历每个节点，取max1+max2+1的最大值就是答案。(如果是直链，说明max2=0)

遍历代码如下：

private static int dfs(int a, int p) {
    int max1 = 0; // 最高子树高度
    int max2 = 0; // 次高子树高度
    for (int i = head[a]; i > 0; i = nxt[i]) { // 遍历子树
        int b = to[i];
        if (b == p) continue; // 跳过父节点
        int depth = dfs(b, a); // 子树高度
        if (depth >= max1) { // 更新max1和max2(前两名可能同样高)
            max2 = max1;
            max1 = depth;
        } else if (depth > max2) { // 更新max2
            max2 = depth;
        }
    }
    ans = Math.max(ans, max1 + max2 + 1); // 最大值
    return max1 + 1; // 当前子树高度是最高子树高度+1
}

发表于今天 10:16:05 回复(0)