题目描述

给定一个含有 $n$ 个节点的 树，以及树中每条边的 权值 $w_{edge_i}$

现需要在树中找出一条 路径，使得该 路径 上所有 边 的 权值之和 最大

分析

这是一道比较经典的 树形DP 题目，我们来一步步来剖析这个问题

我们知道：树上 任意两点 的路径是 唯一 确定的，因此我们可以暴力枚举 起点 和 终点 找出最长路径

如果这样做的话，我们来思考一下时间复杂度：

1. 枚举 起点 和 终点 — $O(n^2)$
2. 找出两点之间的路径长度 — $O(\log n)$

这里找出两点之间的路径有很多种做法，预处理 st 表然后倍增求LCA、树链剖分、Link-Cut Tree

但是光是枚举 起点 和 终点，时间复杂度 就直接拉满了，显然这种做法不可取

既然这 $O(n^2)$ 条路径不能 一一枚举，那么有什么方式可以把他们 分类枚举 呢？

我们考虑换一种 枚举方式：枚举路径的 起点和终点 $\rightarrow$ 枚举路径的 中间节点

我们先讨论一下，对于给定拓扑结构的树里的任意节点，经过他的路径有哪些：

观察我标出的 红色节点，那么经过他的路径有：

1. 以其 子树中的某个节点 作为 起点，以他作为 终点 的 粉色路径
2. 以其 子树中的某个节点 作为 起点，以 子树中的某个节点 作为 终点 的 蓝色路径
3. 以其 子树中的某个节点 作为 起点，以 非其子树的节点 作为 终点 的 橙色路径

对于第 $1$ 种情况，我们可以直接递归处理其子树，找出到当前子树根节点最长的路径长度即可

对于第 $2$ 种情况，我们在处理第 $1$ 种情况时，顺便找出 $1$ 类路径的 次长路径

把 最长 和 次长 拼在一起，就是我们要的第 $2$ 种情况

而对于第 $3$ 种情况，我们可以把它归类为其 祖先节点 的第 $1,2$ 种情况，让其 祖先节点 去处理即可

把上述两类路径的分析，就是如下形式：

DP分析

状态表示—集合$f_{1/2,i}$: 以节点 $i$ 为根的子树中，从子树某个节点到 $i$ 的最长路为 $f_{1,i}$，次长路为 $f_{2,i}$
状态表示—属性$f_{1/2,i}$: 路径长度的最大值 $Max$
状态计算—$f_{1/2,i}$

$$\begin{cases} f_{1,i} = max(f_{1,i_{c_1}} + w_{i,i_{c1}}) &c1 \in i_{child}\\\ f_{2,i} = max(f_{1,i_{c_2}} + w_{i,i_{c2}}) &c2 \in i_{child} ~\&~ c2 \ne c1 ~\&~ f_{2,i} \le f_{1,i} \end{cases}$$

Code

时间复杂度：$O(n)$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e4 + 10, M = N << 1; 

int n;
int h[N], e[M], w[M], ne[M], idx;
int f1[N], f2[N], res;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int father)
{
    f1[u] = f2[u] = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs(j, u);
        if (f1[j] + w[i] >= f1[u]) f2[u] = f1[u] ,f1[u] = f1[j] + w[i]; //最长路转移
        else if (f1[j] + w[i] > f2[u]) f2[u] = f1[j] + w[i];            //次长路转移
    }
    res = max(res, f1[u] + f2[u]);
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dfs(1, -1);
    cout << res;
    return 0;
}