最长距离

最长路径

https://www.nowcoder.com/questionTerminal/430ded6b482d4d8bbcf2eca6f20e62e3

思路

朴素做法

对每个节点做一次dfs,求出其到其他节点的距离,期间保留最大值即可。

时间复杂度

该做法可通过 的数据

Code

class Solution {
#define pii pair<int, int>
#define ll long
private:
    ll ans;
    vector<pii> g[100010];
public:
    void dfs(int x, int fa, int sum = 0) {
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            ans = max(sum + w, ans);
            dfs(v, x, sum + w);
        }
    }
    ll 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]});
        }
        for (int i = 1; i <= n; ++i) {
            dfs(i, i, 0);
        }
        return ans;
    }
};

初步优化

对每个叶节点做一次dfs,求出其到其他叶节点的距离,期间保留最大值即可。

最差时间复杂度

该做法可通过 的数据

Code

class Solution {
#define pii pair<int, int>
#define ll long long
private:
    ll ans;
    vector<pii> g[100010];
public:
    void dfs(int x, int fa, ll sum = 0) {
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            ans = max(sum + w, ans);
            dfs(v, x, sum + w);
        }
    }
    ll 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]});
        }
        for (int i = 1; i <= n; ++i) {
            if (g[i].size() == 1)
                dfs(i, i, 0);
        }
        return ans;
    }
};

标程做法

首先可将该树转化为有根树,考虑为树中的任意两叶节点点的最大距离,不一定经过根节点。
由于是多叉树,最大路径一定是路径和最大的两棵子树的路径和之和。
在dfs过程中可以维护每个结点的两棵最大子树的路径和,保留最大值即可。

时间复杂度

Code

class Solution {
#define pii pair<int, int>
#define maxn 100010
#define ll long long
private:
    int n;
    vector<pii> g[maxn];
    ll f[maxn][2];  //可在dfs过程中用两个变量优化, f[i][0] 表示最大值,f[i][1] 表示次大值
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;
            }
        }
    }
    ll 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);
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            res = max(res, f[i][0] + f[i][1]);
        }
        return res;
    }
};
全部评论
感觉第二种也是O(n),无向图,随便哪个点开始dfs,每次都比较,最后也能求到全局最大
点赞 回复 分享
发布于 2021-05-17 16:03

相关推荐

lxylxy_:其实是美团卷起来了
点赞 评论 收藏
分享
听说改名字就能收到offer哈:Radis写错了兄弟
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务