WA on #5

code:

#include <bits/stdc++.h>
#define int long long
#define inf 1000000000000000000ll
#define double long double
#define MAXN 2005
using namespace std;
int n, K, u, v, w, sz[MAXN], vis[MAXN], dp[MAXN][MAXN];
vector<pair<int, int> > e[MAXN], son[MAXN];
void dfs(int id)
{
    sz[id] = 1;
    vis[id] = 1;
    for (pair<int, int> i : e[id])
    {
        if (vis[i.first])
        {
            continue;
        }
        son[id].push_back(i);
        dfs(i.first);
        sz[id] += sz[i.first];
    }
}
void dfsdp(int id)
{
	dp[id][0] = dp[id][1] = 0;
    // cout << "dfsdp " << id << " " << son[id].size() << endl;
    for (pair<int, int> SON : son[id])
    {
        dfsdp(SON.first);
    }
    for (pair<int, int> SON : son[id])
    {
        int len = SON.second;
        int j = SON.first;
		for (int k = min(K, sz[id]); k >= 0; k--)
        {
        	int maxn = 0;
        	if (dp[id][k] != -1 && sz[j] <= n - K)
        	{
        		maxn = dp[id][k] + dp[j][0] + len * sz[j] * (n - K - sz[j]);
        	}
            for (int l = min(k, sz[j]); l >= 0; l--)
            {
            	if (dp[id][k - l] == -1)
            	{
            		break;
            	}
                maxn = max(maxn, dp[id][k - l] + dp[j][l] + len * (l * (K - l) + (sz[j] - l) * (n - K - sz[j] + l)));
                // cout << k << " " << len << " " << l << " " << l * (K - l) << " " << (sz[j] - l) * (n - K - sz[j] + l) << endl;
            }
            dp[id][k] = maxn;
        }
    }
    // cout << "dp[" << id << "] : ";
    // for (int i = 0; i <= K; i++)
    // {
        // cout << dp[id][i] << " ";
    // }
    // cout << endl;
}
signed main()
{
	memset(dp, -1, sizeof(dp));
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> K;
    for (int i = 1; i < n; i++)
    {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1);
    dfsdp(1);
    cout << dp[1][K];
    return 0;
}

一年前的我也是 WA on #5，如果你觉得我上面这份代码太不可读了，可以帮我调下面的，逻辑一样：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x, y, z, b, w, a[2005], fa[2005], vis[2005], snum[2005], dp[2005][2005], dp2[2005][2005], sz[2005];
vector<pair<int,int> > v[2005], s[2005];
int dfsmaketree(const int id)
{
	vis[id] = 1;
	sz[id] = 1;
	for (register auto i : v[id])
	{
		if (!vis[i.first])
		{
			fa[i.first] = id;
			s[id].push_back(i);
			snum[id]++;
			sz[id] += dfsmaketree(i.first);
		}
	}
	return sz[id];
}
void dfs(const int id)
{
	dp[id][0] = dp[id][1] = 0;
	for (register auto i : s[id])
	{
		const int t = i.first;
		dfs(t);
		for (register int j = min(b,sz[id]); j >= 0; j--) //现在id子树的black
		{
			register int maxn = 0;
			if (dp[id][j] != -1)
				maxn = dp[id][j] + dp[t][0] + sz[t] * (w - sz[t]) * i.second;
			for (register int k = 0; k <= j; k++) //现在i子树的black
			{
				if (dp[id][j - k] == -1) continue;
				if (sz[t] < k)
				{
					break;
				}
				maxn = max(maxn,dp[id][j - k] + dp[t][k] + i.second * ((b - k) * k + (sz[t] - k) * (w - sz[t] + k)));
			}
			dp[id][j] = maxn;
		}
	}
}
signed main()
{
	cin >> n >> b;
	w = n - b;
    memset(dp,-1,sizeof(dp));
// 	if (b > w)
// 	{
// 	    swap(w,b);
// 	}
	for (register int i = 1; i < n; i++)
	{
		cin >> x >> y >> z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
//	for (int i = 1; i <= n; i++)
//	{
//		cout << v[i].size() << " ";
//	}
//	cout << endl;
	dfsmaketree(1);
//	for (int i = 1; i <= n; i++)
//	{
//		cout << s[i].size() << " ";
//	}
//	cout << endl;
	dfs(1);
//	for (int i = 1; i <= n; i++)
//	{
//		cout << sum[i] << " ";
//	}
//	cout << endl;
//	for (int i = 1; i <= n; i++)
//	{
//		cout << cnt[i] << " ";
//	}
//	cout << endl;
	cout << dp[1][b];
	return 0;
}

错误数据：

读入：

100 45
2 1 8511
3 1 5379
4 2 8061
5 4 7321
6 1 496
7 1 7882
8 5 1887
9 1 347
10 5 5976
11 6 6021
12 5 3841
13 1 7496
14 10 6793
15 5 8597
16 6 6993
17 7 9521
18 12 4166
19 13 6941
20 9 6705
21 13 9455
22 15 977
23 19 8303
24 17 1396
25 1 4346
26 21 2199
27 11 8301
28 13 7229
29 20 8757
30 21 3621
31 24 1785
32 17 7046
33 7 4120
34 13 9617
35 25 2491
36 10 3360
37 7 971
38 13 3281
39 1 461
40 28 2921
41 25 3587
42 18 4321
43 34 2801
44 1 5331
45 11 6627
46 29 7108
47 22 6401
48 34 1559
49 7 4281
50 12 7124
51 31 8020
52 40 8804
53 22 4937
54 43 6801
55 49 9131
56 41 6258
57 14 2945
58 28 8989
59 30 6680
60 12 7074
61 50 2701
62 13 5237
63 25 6943
64 1 5399
65 1 2865
66 41 6535
67 1 1285
68 4 2102
69 6 7938
70 68 4993
71 51 9281
72 22 4179
73 6 9201
74 15 5329
75 25 3324
76 61 2666
77 53 5459
78 59 4241
79 73 3461
80 53 2125
81 9 3117
82 54 3745
83 14 2372
84 77 5009
85 43 1631
86 22 8199
87 9 8933
88 38 7341
89 45 1853
90 44 7781
91 1 973
92 51 2605
93 9 8865
94 10 1081
95 7 7929
96 60 4145
97 37 2955
98 84 1591
99 57 1161
100 70 7769

答案：

90022046

我的输出：

90169860