题解 | #最长路径#

题目描述
城市 A 新建了 n 个座房子，城市规划处用 n−1 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。

方法一：暴力解法

求解思路
对于求解本题，我们可以将房子看作节点，双向街道看作边，即n个节点，n-1条边，可以构成树。我们对每个叶节点做一次dfs，求出到其它叶节点的距离，然后我们保留最大值即可。

图片说明

解题代码

class Solution {
#define pii pair<int, int>
private:
    long long myans;
    vector<pii> g[100000];
public:
    void dfs(int x, int fa, long long sum = 0) 
    {   //dfs
        for (auto cur: g[x])
        {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            myans = max(sum + w, myans);
            dfs(v, x, sum + w); // 继续dfs即可
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for (int i = 0; i < n - 1; ++i)
        {
            g[u[i]].push_back({v[i], w[i]});
            g[v[i]].push_back({u[i], w[i]});
        }
        for (int i = 1; i <= n; ++i)
        {   //对每个叶节点做dfs
            if (g[i].size() == 1)
                dfs(i, i, 0);
        }
        return myans; // 返回结果即可
    }
};

复杂度分析
时间复杂度：使用到了dfs，与树的深度有关，因此时间复杂度为 $O(N)$
空间复杂度：引入常数级数组g[100010],因此空间复杂度为 $O(1)$

方法二：优化求解

求解思路
对于本题的求解，我们可以将该树转化为有根树，考虑树中任意两叶节点的最大距离，其中不需要经过根节点，然后通过dfs维护每个节点的最大子树的路径和，最后即可求出本题的答案。

图片说明

解题代码

class Solution {
#define pii pair<int, int>
#define maxn 100000
private:
    int n;
    vector<pii> g[maxn];
    long long f[maxn][2];
public:
    void dfs(int x, int fa = 0)
    {
        for (auto cur: g[x])
        {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            dfs(v, x);
            if (f[x][0] < f[v][0] + w) // 比较树中任意两叶节点的距离
            {
                f[x][1] = f[x][0];
                f[x][0] = f[v][0] + w;
            }
            else if (f[x][1] < f[v][0] + w)
            {
                f[x][1] = f[v][0] + w;
            }
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        for (int i = 0; i < n - 1; ++i)
        {
            g[u[i]].push_back({v[i], w[i]}); // 遍历每个叶节点
            g[v[i]].push_back({u[i], w[i]});
        }
        dfs(1, 0);
        long long myres = 0;
        for (int i = 1; i <= n; ++i)
        {
            myres = max(myres, f[i][0] + f[i][1]); // 保存最大值
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：使用递归，因此时间复杂度为 $O(N)$ ,其中N为树的深度
空间复杂度：引入常数级变量空间，因此空间复杂度为 $O(1)$