题解 | #树的直径#

树形DP

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

class Solution {
public:
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    int ans = 0;
    int d1[100005] = {0}, d2[100005] = {0};
    unordered_map<int, vector<pair<int, int>>> E;
    void dfs(int u, int fa) {
        d1[u] = 0;
        d2[u] = 0;
        for (auto v : E[u]) {
            if (v.first == fa) continue;
            dfs(v.first, u);
            int t =  d1[v.first] + v.second;
            if (d1[u] < t) {
                d2[u] = d1[u];
                d1[u] = t;
            } else if (d2[u] < t) {
                d2[u] = t;
            }
        }
        ans = max(ans, d1[u] + d2[u]);
    }
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        for (int i = 0; i < n - 1; i++) {
            E[Tree_edge[i].start].push_back({Tree_edge[i].end, Edge_value[i]});
            E[Tree_edge[i].end].push_back({Tree_edge[i].start, Edge_value[i]});
        }
        dfs(0, -1);
        return ans;
    }
};