最长距离

思路

朴素做法

对每个节点做一次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;
    }
};