树形DP - 详细解释
题目描述
给定一棵树,树中包含 $n$ 个结点(编号$1$~$n$)和 $n-1$ 条无向边,每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说,要找到一条路径,使得使得路径两端的点的距离最远。
注意:路径中可以只包含一个点。
输入格式
第一行包含整数 $n$。
接下来 $n-1$ 行,每行包含三个整数 $a_i,b_i,c_i$,表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。
输出格式
输出一个整数,表示树的最长路径的长度。
数据范围
$1 \\le n \\le 10000$,
$1 \\le a_i,b_i \\le n$,
$\-10^5 \\le c_i \\le 10^5$
输入样例:
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
输出样例:
22
算法
建树:给出的(a, b, c)没有明确指出a和b的父子关系,干脆建成无向图,搜索时多增加一个参数避免往上搜索即可
搜索时,确定一点作为根节点,这样唯一确定了树的拓扑结构
(下图是同一张无向图,在确定根节点后,树的父子关系随之确定。根节点可以取任一点)
穷举所有路径太费时,我们通过DP化整为零!将繁多的路径归为有限的几类,一次求解一个类。
树中所有的路径均有一系列点构成,那怎么化整为零呢?可以按照根节点的不同来将路径归类。
即将“根节点”(高度比所有点都低的点)相同的路径归为一类。(一条确定的路径中只会有一个“根节点”)
以上图左为例,路径2 6 1 4
和5 1 4
都是一类,它们的“根节点”都为1,1是路径中高度最低的点
那么以某节点为根节点的最长路径应该等于以该节点出发到不同子树的最长路径和次长路径之和(不能重复到不同子树),比如下图这俩。注意:不能同时取1 6 2
和1 6 3
。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4+10, M = N*2;
int h[N], e[M], ne[M], w[M], idx=0;
int n;
int res = 0; //最小是0,最短的路径只包含一个点
void init()
{
memset(h, -1, sizeof h);
idx = 0;
}
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 返回root节点上的最长路径, father参数避免root向上搜索
int dfs(int root, int father)
{
int d1 = 0, d2 = 0; //root所有子树中dfs值最大的前两个
for(int i=h[root]; i!=-1; i=ne[i])
{
int j = e[i]; //root -> j
if(j == father) continue;
int sub_dist = dfs(j, root) + w[i];
if(sub_dist >= d1) //注意这里是>=
d2 = d1, d1 = sub_dist;
else if(sub_dist > d2)
d2 = sub_dist;
}
res = max(res, d1+d2); //当前根节点最长的两棵子树长度之和
return d1;
}
int main()
{
init();
cin >> n;
for (int i = 0; i < n-1; i ++ )
{
int a, b ,c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c); //这里不知道谁是谁的父亲,干脆建成无向图
}
// for(int i=1; i<=n; i++)
// {
// printf("%d :", i);
// for(int j=h[i]; j!=-1; j=ne[j])
// {
// int k=e[j];
// printf("%d ", k);
// }
// cout << endl;
// }
dfs(1, -1); //从任意节点开始递归都可以
cout << res << endl;
return 0;
}