树形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;

}