树形dp
涉及不重复背包组合求最小
从边长分段看不好入手
因为点数只有100点值<=2,总值<=200
可以对每个点的每个值进行dp
这里最后不回来肯定优于全回来
然后由于要分为回来和不回来两种情况要分别dp,因为不回来会要用到回来的
不回来的可以按不回来的最小+去掉不回来那个子节点的回来的最小进行dp
另外注意下上下限和初始值
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 205;
int vec[N];
struct Edge{
int v, len, nxt;
}edge[N];
int cnt;
int head[N];
int dp[2][N][N];
void addedge(int u, int v, int value) {
edge[cnt] = Edge{ v,value,head[u] };
head[u] = cnt++;
edge[cnt] = Edge{ u,value,head[v] };
head[v] = cnt++;
}
void dfs(int u,int p) {
dp[0][u][vec[u]] = 0;
dp[1][u][vec[u]] = 0;
for (int t = head[u]; t != -1; t = edge[t].nxt) {
Edge e = edge[t];
if (e.v == p)
continue;
dfs(e.v, u);
int v = e.v;
for (int i = 200; i >= 0; i--)
{
for (int j = 0; j <= i; j++) {
dp[0][u][i] = min(dp[0][u][i],dp[0][u][j] + dp[0][v][i-j]+2*e.len);
}
}
}
for (int t = head[u]; t != -1; t = edge[t].nxt) {
Edge e = edge[t];
int v = e.v;
if (v == p)
continue;
int sum[N];
for (int i = 0; i <= 202; i++)
sum[i] = 1e9;
sum[vec[u]] = 0;
for (int t2 = head[u]; t2 != -1;t2=edge[t2].nxt) {
Edge e2 = edge[t2];
int v2 = e2.v;
if (v2==p || v2 == v)
continue;
for (int i = 200; i >= 0; i--){
for (int j = 0; j <= i; j++) {
sum[i] = min(sum[i], sum[j] + dp[0][v2][i - j]+2*e2.len);
}
}
}
for (int i = 200; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[1][u][i] = min(dp[1][u][i], dp[1][v][j] + sum[i - j]+e.len);
}
}
}
}
int main() {
int n;
cin >> n;
cnt = 1;
for (int i = 1; i <= n; i++) {
cin >> vec[i];
}
memset(head, -1, sizeof head);
for (int i = 0; i < 2; i++)
for (int j = 0; j <= 200; j++)
for (int k = 0; k <= 200; k++)
dp[i][j][k] = 1e9;
for (int i = 0; i < n - 1; i++) {
int sv, ev, w;
cin >> sv >> ev >> w;
addedge(sv,ev,w);
}
dfs(1, 0);
int m;
cin >> m;
while(m--){
int x;
cin >> x;
for (int i = 200; i >=0; i--)
if (dp[1][1][i] <= x)
{
printf("%d\n", i);
break;
}
}
return 0;
}