AcWing 4620. 旅行 树形DP，记忆化搜索
题目描述
给定一个 n 个节点的树，节点编号为 1∼n。
请你从中选择一个简单路径（不能包含重复节点或重复的边），并沿所选路径来一场旅行，更具体的说，就是从所选路径的一个端点沿路径前往另一个端点。
注意，所选简单路径可以只由一个节点组成。
旅行需要花费能量。
初始时，你的能量为 0。
在旅行过程中：
- 每经过一个节点（包括起点和终点），就可以得到该节点的能量，其中节点 i 包含的能量为 wi。
- 每经过一条边 (u,v)，就需要消耗一定的能量 c。
你设计的旅行路线应满足：
在经过任何一条边之前，你的现有能量都不能少于该边所需消耗的能量（否则，将无法顺利通过该边）。
在满足条件 1 的前提下，旅行结束时，剩余的能量尽可能大。
请计算并输出剩余能量的最大可能值。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 w1,w2,…,wn。
接下来 n−1 行，每行包含三个整数 u,v,c，表示存在一条边 (u,v)，经过它所需的能量为 c。
保证给定图是一棵树。
输出格式
一个整数，表示剩余能量的最大可能值。
数据范围
前 3 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤3×105，0≤wi≤109，1≤u,v≤n，u≠v，1≤c≤109。
输入样例1：
3
1 3 3
1 2 2
1 3 2
输出样例1：
3
输入样例2：
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
输出样例2：
7
思路
如果没有第一个条件的限制，那么这就是一个求树的直径的问题。在树上找到两个点，这两个点的树上距离最大。
但是现在有一个全称不能小于0的限制，还能转化成求树的直径的问题吗？
我们现在想一下，在求树的直径的过程中，会经过权值为负数的点嘛？
显然是不会的，那么我们在遍历的过程中，遇到负数的情况，直接跳过就行了。
yxc那个解释我听不明白，他说的去掉，我感觉只是代码上的等价，因为那段代码去掉之后，确实不影响正确性。
出题人就是有可能给你加一个多余的限制条件来阻碍你的思维，但是其实这个条件是没有用的。这就是和别人差距的地方。
时间复杂度
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 300010, M = N << 1;
int n;
int v[N];
int h[N], e[M], ne[M], w[M], idx;
LL f[N]; // 到达N剩余的最大能量
LL ans;
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 fa) {
LL max1 = 0, max2 = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
// 求子节点的, 这个很关键。
dfs(j, u);
// 这个去掉也是可以的
// if (f[j] - w[i] < 0) continue;
// 更新最大值
if (f[j] - w[i] >= max1) {
max2 = max1;
max1 = f[j] - w[i];
}
// 更新次大值
else if (f[j] - w[i] > max2) {
max2 = f[j] - w[i];
}
}
// 更新全局ans
ans = max(ans, v[u] + max1 + max2);
// f[u] 只会计算一次。
f[u] = v[u] + max1;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n ; i ++ ) scanf("%d", &v[i]);
for (int i = 1; i < n; i ++ ) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dfs(1, -1);
cout << ans << endl;
return 0;
}