<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
题目描述
给定一棵树,树中包含 $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
算法1
(树形DP) $O(n)$
在树形动态规划当中,我们一般先算子树再进行合并,在实现上与树的后序遍历相似,都是先遍历子树,遍历完之后将子树的值传给父亲。简单来说我们动态规划的过程大概就是先递归访问所有子树,再在根上合并
一开始,我的思路是:
$f[i][0]$ 表示在子树 $i$ 内,以 $i$ 为端点的某条直线(有一端点点在子树 $i$ 内,另一个端点为 $i$)
$f[i][1]$ 表示在子树 $i$ 内,以 $i$ 为某直线中的一个点(两端点都在子树 $i$ 内,且不为 $i$)
$f[i][0]$ = $max(f[i.edge][0] + w[i.edge])$;
$f[i][1]$ = $f[i][0] + second max(f[i.edge][0] + w[i.edge])$;
但事实上,$f[i][0] \leqslant f[i][1]$
所以 $f[i][0]$ 不可能是ans!
所以在代码中,我们改一下:
$f’[i][0]$ 表示以 i 为端点的某最长路径长度
$f’[i][1]$ 表示以 i 为端点的某次长路径长度
$(f’[i][0] + f’[i][1] = f[i][1])$
代码中有一个 $ans = max$ 操作,其中 $f[root][0] + f[root][1]$ 为前文的 $f[i][1]$
于是乎:我们将 $f’[i][j]$ 直接替换为 $f[i][j]$
状态表示—集合$f_{0/1,i}$: 以节点 $i$ 为根的子树中,从子树某个节点到 $i$ 的最长路为 $f_{0,i}$,次长路为 $f_{1,i}$
状态表示—属性$f_{0/1,i}$: 路径长度的最大值 $Max$
状态计算—$f_{0/1,i}$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 40009;
struct node { int to, w; };
bool v[N];
vector <node> edge[N];
int n, ans, f[N][2];
void read()
{
cin >> n;
for(int i = 1, a, b, c;i <= n - 1;++ i)
{
f[i][0] = f[i][1] = 0; v[i] = false;
cin >> a >> b >> c;
edge[a].push_back((node) {b, c});
edge[b].push_back((node) {a, c});
}
return;
}
void dfs(int root, int father)
{
for(int i = 0, j, u;i < edge[root].size();++ i)
{//枚举每一个儿子
if(edge[root][i].to == father) continue; //不能递归父节点
dfs(edge[root][i].to, root);//根变为子节点,子节点的父节点就是当前节点
j = edge[root][i].to, u = edge[root][i].w;//简化表达式
if (f[j][0] + u >= f[root][0]) f[root][1] = f[root][0] ,f[root][0] = f[j][0] + u;//更新 f[root][0]
else if (f[j][0] + u > f[root][1]) f[root][1] = f[j][0] + u;//更新 f[root][1]
}
ans = max(ans, f[root][0] + f[root][1]);// 更新ans
return;
}
int main()
{
read();//读入
dfs(1, -1);//求解 DP
cout << ans << endl;
return 0;
}