题目

一个国家由 n 个城市组成，这 n 个城市由 n?1 条双向道路连接，呈一个树形结构。

每个城市都设有加油站，在第 i 个城市可以购买 wi 升汽油。

汽车在道路上行驶，毫无疑问也会消耗汽油，每条道路的具体耗油量也会给出。

现在，需要制定一条汽车的行进路线，从任意城市 s 出发，经过一条简单路径，到达任意城市 e 结束。

注意，行进路线也可以只包含一个城市（也就是哪都没去）。

汽车初始时油箱是空的，但是可以在路线中经过的每个城市购买汽油，包括开始城市和最终城市。

如果在一条行进路线中，汽车沿一条道路从某一城市开往另一城市时，现有油量小于该条道路所需油量，那么就说明这条行进路线行不通。

请问，在保证行进路线合理的情况下，汽车在抵达最终城市后，可以剩余的最大油量是多少？

再次提醒，汽车在最终城市也可以加油。

输入输出

输入：第一行包含整数 n。

第二行包含 n 个整数 w1,w2,…,wn。

接下来 n?1 行，每行包含三个整数 u,v,c，表示城市 u 和城市 v 之间存在一条双向道路，耗油量为 c。
输出：一个整数，表示可能的最大剩余油量。

思路

这道题是选出一条路径使最大剩余油量最大，即树的最长路径（树的直径）问题。点权为正，边权为负。
可以枚举一条路径的最高点，该点的最长路径由根节点的点权+子树的最长长度+子树的次长长度。用递归来做，递归返回的是子树往下的最长长度，计算出后，更新最长路径长度。写的太混乱了

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 300010;typedef long long LL;int tot;int head[N << 1],ver[N << 1], nxt[N << 1],edge[N << 1];int w[N];LL ans;void add(int u, int v, int c) // 添加一条边a->b{ ver[++tot] = v; nxt[tot] = head[u]; head[u] = tot; edge[tot] = c;}LL dfs(int u,int fa){ LL max1=0,max2=0; //以u为根节点的子树中最大的长度和次大的长度 for(int i = head[u];i;i = nxt[i]){ int v = ver[i]; if(v == fa) continue; LL d = dfs(v,u); //d是以v为根节点的子树的最长路径 if(d < edge[i]) continue; d -= edge[i]; //走子树到根节点需要耗费油量 if(d >= max1) max2 = max1,max1 = d; //先更新max2，再更新max1 else if(d > max2) max2 = d; } ans = max(ans, max1 + max2 + w[u]); return max1 + w[u]; //返回的是以u为根节点的最长路径}int main(){ int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> w[i]; for (int i = 0; i < n-1; i ++ ){ int u,v,c; cin >> u >> v >> c; add(u, v, c); add(v, u, c); } dfs(1,0); cout << ans;}