Solution
考虑树形 \(dp\)。
我们可以注意到节点 \(i\) 的相邻的边中被选中的不超过 \(d_i\) 条，显然我们可以定义状态 \(dp_{u,k}\) 表示节点 \(u\) 连接子节点的边有 \(k\) 条的最大值。
但是此处没有给定 \(d_i\) 的范围，所以对于一个节点最多可能会有 \(n-1\) 个点，所以时间复杂度和空间的复杂度都是无法接受的。
既然考虑一个点与子节点之间边的情况不行，那么是否可以反过来想，考虑当前点是否与父节点相连的情况，此时每一个点只有与父节点的边选与不选两种情况。
现在我们重新定义状态，设 \(dp_{u,0/1}\) 为当前点为 \(u\)，是否与父节点连边的最大值。
但是在求解的过程中我们需要保证每个节点 \(i\) 相连的边不超过 \(d_i\) 条。
我们可以发现不选与子节点的边一定是一种情况，我们首先可以定义一个变量 \(sum\) 为当前点 \(u\) 与其任意一个子节点 \(v\) 的边都不选。
此时如果我们选择其中一个节点与其的连边，那么这时答案的增量记为 \(\Delta_{v} = dp_{v, 1} + w(u, v) - dp_{v, 0}\)。
此时我们选出的就是最大的几个正数，由于不超过 \(n\) 个，考虑直接排序。
对于 \(dp_{u,1}\) 选出只需最大的 \(d_u - 1\) 个，应为它需要连接父节点。
特殊的，如果 \(d_u = 0\)，那么 \(dp_{u, 1}\) 不存在，应赋值为极小值。
若我们假定这棵树的根节点为 \(1\)，那么答案为 \(\max\{ dp_{1, 0}, dp_{1, 1}\}\)。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
#define inl inline
using namespace std;
const int N = 3e5, INF = 1e9;
int n;
int d[N + 5];
int dp[N + 5][2];
struct Edge {
int v, w;
Edge () {}
Edge (int vv, int ww) : v(vv), w(ww) {}
};
vector<Edge> G[N + 5];
inl bool cmp(int x, int y) { return x > y; }
inl void dfs(int u, int fa) {
int sum = 0;
vector<int> stk;
for (auto it : G[u]) {
int v = it.v, w = it.w;
if (v == fa)
continue;
dfs(v, u), sum += dp[v][0];
stk.push_back(dp[v][1] - dp[v][0] + w);
}
sort(stk.begin(), stk.end(), cmp);
for (int i = 0; i < min((int)stk.size(), d[u] - 1); i++)
sum += max(0ll, stk[i]);
dp[u][0] = sum + ((d[u] && stk.size() > d[u] - 1) ? max(0ll, stk[d[u] - 1]) : 0);
dp[u][1] = !d[u] ? -INF : sum;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> d[i];
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
G[u].push_back(Edge(v, w)), G[v].push_back(Edge(u, w));
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]);
return 0;
}