NC99 树的直径

题目描述

给定一棵树，求出这棵树的直径，即树上最远两点的距离。

1. Floyd算法（不合要求）

求出全局任意两点间距离，找最大值即可。

代码较简单且不合要求，不再赘述。

时间复杂度: $O (n^{3})$ , 3重循环。
空间复杂度： $O (n^{2})$ , 需要使用邻接矩阵存图。

2. 两趟dfs/bfs

思路一的复杂度显然太高了，我们不需要算那么多冗余的东西。

从任意一个点出发（通常是1号点），dfs或bfs这棵树，找到离这个点最远的点，记为s，再从s开始搜，找离s最远的点记为t，s到t的距离即是直径。

alt

/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 */

class Solution {
public:
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    static const int N = 20010; 
    static const int INF = 0x3f3f3f3f; // 定义初始距离为无穷大
    
    struct Edge {
        int to, next, dis; // 存储图
    } e[N << 1];
    
    int head[N], idx = 1;
    
    void add(int a, int b, int c) {
        e[idx].to = b;
        e[idx].next = head[a];
        e[idx].dis = c;

        head[a] = idx++;
    }
    
    int far = -1; // 最远距离在的点
    int res = -1; // 最远距离
    
    void dfs(int u, int f = -1, int d = 0) {
        if (d > res) res = d, far = u;
        
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].dis;
            if (v != f) 
                dfs(v, u, d+w);
        }
    }
    
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        memset(head, -1, sizeof(head));
        
        for (int i = 0; i < n-1; i++) {
            add(Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]);
            add(Tree_edge[i].end, Tree_edge[i].start, Edge_value[i]);
        }
        
        dfs(1);
        dfs(far);
        
        return res;
    }
};

时间复杂度: $O (n)$ , 每个点遍历2次。
空间复杂度： $O (n)$ , 链式前向星存图，空间复杂度是 $O (n + (n - 1))$ , 仍视为 $O (n)$

3. 树形DP

还有一种做法，只需要1趟dfs，但理解难度略大一些。

我们令dp[u][1]和dp[u][2]分别表示以u为根的子树距离的最大值和次大值。因为直径所在的两个点必有一个lca，而从lca出发的所有路径里，最大和次大的两条一定是直径所在。因此我们计算出每个点的dp[u][1]和dp[u][2]值，取他们和的最大值，就一定是直径。

转移关系的理解就是，先后根序dfs这棵树，每遍历到一个点，就递归遍历它的所有儿子，这样其儿子的dp值已经算好，然后看每个儿子的dp值+当前节点的距离是否比次大值大，如果大，则更新次大值，如果比最大值还大，那么更新到最大值，同时最大值变成次大值。

进一步观察dp的性质发现，我们只需要维护当前节点的dp值，以及子节点dp值的前两名即可，因此我们不需要实质性定义dp数组，只需要在dfs(u)函数的返回值里把dp[u][1]丢出来即可。

上代码：

/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 */

class Solution {
public:
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    static const int N = 20010; 
    static const int INF = 0x3f3f3f3f; // 定义初始距离为无穷大
    
    struct Edge {
        int to, next, dis; // 存储图
    } e[N << 1];
    
    int head[N], idx = 1;
    
    void add(int a, int b, int c) {
        e[idx].to = b;
        e[idx].next = head[a];
        e[idx].dis = c;

        head[a] = idx++;
    }
    
    int res = -1;
    
    int dfs(int u, int f = -1) {
        int max1 = 0, max2 = 0;

        for (int i = head[u]; ~i; i = e[i].next) {
            int j = e[i].to, w = e[i].dis;
            
            if (j != f) {
                int t = dfs(j, u) + w; // 即原来的dp[j][1]+w
                if (t > max1) max2 = max1, max1 = t;
                else if (t > max2) max2 = t;
                
                res = max(res, max1+max2); // 更新可能的最大解
            }
        }
        return max1; // return dp[u][1]给上层用
    }
    
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        memset(head, -1, sizeof(head));
        
        for (int i = 0; i < n-1; i++) {
            add(Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]);
            add(Tree_edge[i].end, Tree_edge[i].start, Edge_value[i]);
        }
        
        dfs(1);
        
        return res;
    }
};

时间复杂度: $O (n)$ , 每个点遍历1次。常数是方法2的一半
空间复杂度： $O (n)$ , 链式前向星存图,dp数组省略了。

题解 | #树的直径#

NC99 树的直径

题目描述

1. Floyd算法（不合要求）

2. 两趟dfs/bfs

3. 树形DP