把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1083A The Fair Nut and the Best Path
题目大意：树的每个节点上可以加w[i]的油，节点之间的边有距离e[i]，会消耗等同距离数量的油，求一条路径使得走完之后剩余的油量最多。

解：

就是普通的树形dp，遍历的时候判断一下这条路是否能走，dp[i]记录的是从叶子走到i时获得的最大油量。
但有可能会出现这样的情况：当节点u和其儿子v间的路径大于dp[v]时，显然我判断为不能走这条路，但实际上我可以从u走到v，如果从另一条路走到u节点的过程中u获得了足以走这条路的油那么实际上我可以这样走到v。
于是我写了两个dfs，一个进行树形dp后序遍历，一个进行前序遍历去更新我所说的情况中被更新的值。
结果发现dfs2去掉之后也还是可以ac？？
如果我说的情况确实存在且影响最大值，那么显然这个v节点值得我去花这条路径的路长来获取，而且从另一条路走到u的时候我的油量是大于路长的，也就是说首先w[v]>e[u,v]。
哦，如果这个式子成立的话第一次好像就能走了。
我是sb。
树形dp本身还是比较套路化的，保不齐为了坑人就出了什么特殊条件，这次虽然是自作聪明了，不过也算是为以后做准备吧（挣扎）。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
using namespace std;
map<pll, ll> dis;
ll wei[maxn],dp[maxn],from[maxn],rcd[maxn];
vector<ll> tree[maxn];
ll ans;
bool cmp(ll l1, ll l2) { return l1 > l2; }
void dfs(int n, int dad) {
	int siz = tree[n].size();
	ll res = wei[n];
	vector<ll> diss;
	int mxd = 0;
	inc(i, 0, siz) {
		int son = tree[n][i];
		if (son == dad)continue;
		dfs(son, n);
		pll p;
		p.first = n, p.second = son;
	//	cout << "n = " << n << " dis from " << son << " = " << dis[p] << endl;
		if (dp[son] >= dis[p]) {
			if (dp[son] - dis[p] > 0) {
				diss.push_back(dp[son] - dis[p]);
				if (dp[son] - dis[p] >= mxd) {
					rcd[n] = son;
					if (dp[son] - dis[p] == mxd)rcd[n] = -1;
				}
			}
		}
	}
	sort(diss.begin(), diss.end(),cmp);
	if (diss.size() >= 2) {
		ans = max(ans, res + diss[0] + diss[1]);
	}
	if (diss.size() >= 1)res =max(res,res+diss[0]);
	dp[n] = res;
	ans = max(ans, dp[n]);
	//cout << "dp." << n << " = " << dp[n] << endl;
}
//void dfs2(int n, int dad) {
//	int siz = tree[n].size();
//	inc(i, 0, siz) {
//		int son = tree[n][i];
//		if (son == dad)continue;
//		if (rcd[n] == son)continue;
//		dfs2(son, n);
//		pll p;
//		p.first = n, p.second = son;
//		if (dp[n] >= dis[p]) {
//			dp[son] = max(dp[son], wei[son]+dp[n] - dis[p]);
//		}
//	}
//	ans = max(ans, dp[n]);
//}
int main() {
	cfast;
	int n;
	cin >> n;
	inc(i, 1, n + 1)cin >> wei[i];
	int nn = n - 1;
	while (nn--) {
		ans = 0;
		ll a, b, c;
		cin >> a >> b >> c;
		tree[a].push_back(b);
		tree[b].push_back(a);
		pll p, p2;
		p.first = a, p.second = b;
		p2.first = b, p2.second = a;
		dis[p] = c;
		dis[p2] = c;
	}
	dfs(1, -1);
	//inc(i, 1, n + 1)cout << dp[i] << " ";
	//dfs2(1, -1);
	cout << ans << endl;
}