题目
有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并
将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。输入格式
第一行两个整数N,K。
接下来N-1行每行三个正整数fr,to,dis,表示该树中存在一条长度为dis的边(fr,to)。 输入保证所有点之间是联通的。 N<=2000,0<=K<=N输出格式
输出一个正整数,表示收益的最大值。
输入样例
5 2
1 2 3
1 5 1
2 3 1
2 4 2
输出样例
17
提示
【样例解释】
将点1,2染黑就能获得最大收益。
题解
我dp真是太弱了
我们考虑把点与点间的贡献转移到边上
对于一条边\((u,v)\),我们记\(u\)一侧的黑点数为\(b_u\),白点数为\(w_u\),\(v\)一侧类似 那么该边的贡献就为\[w_{(u,v)} * (b_u * b_v + w_u * w_v)\]那么我们改变一下:\(f[i][j]\)表示\(i\)为根的子树中选\(j\)个黑点,此时子树中的边产生的最大贡献
那么就很好转移了 对于节点\(i\),其子树的贡献已经算出,我们只需要考虑其到子树的边的贡献即可 我们枚举其儿子\(t\),并枚举儿子选的黑点数,再枚举剩余的子树的黑点数计入贡献乍一看似乎\(O(n^3)\)
仔细分析一下,我们枚举的是子树的大小,每个子树产生的复杂度为\(O(siz[t] * (siz[u] - siz[t]))\),就相当于该子树的点与剩余子树的点形成的点对的个数 也就是说,我们实质在枚举点对,而且容易发现,每对点对只会在其\(lca\)处被枚举 所以可以保证是\(O(n^2)\)的#include#include #include #include #include #define LL long long int#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define BUG(s,n) for (int i = 1; i <= (n); i++) cout< <<' '; puts("");using namespace std;const int maxn = 2005,maxm = 10005,INF = 1000000000;inline LL read(){ LL out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int h[maxn],ne = 2;struct EDGE{int to,nxt; LL w;}ed[maxm];inline void build(int u,int v,LL w){ ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++; ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++;}LL f[maxn][maxn],t[maxn];int siz[maxn],fa[maxn],n,K;inline void cmax(LL& a,LL b){if (a < b) a = b;}void dfs(int u){ siz[u] = 1; for (int i = 2; i <= n + 1; i++) f[u][i] = -INF; Redge(u) if ((to = ed[k].to) != fa[u]){ fa[to] = u; dfs(to); for (int i = 0; i <= siz[u] + siz[to]; i++) t[i] = -INF; for (int i = 0; i <= siz[u]; i++) for (int j = 0; j <= siz[to]; j++) cmax(t[i + j],f[u][i] + f[to][j] + ed[k].w * (j * (K - j) + (siz[to] - j) * (n - K - (siz[to] - j)))); siz[u] += siz[to]; for (int i = 0; i <= siz[u]; i++) f[u][i] = t[i]; }}int main(){ n = read(); K = read(); int a,b; LL w; for (int i = 1; i < n; i++){ a = read(); b = read(); w = read(); build(a,b,w); } dfs(1); printf("%lld\n",f[1][K]); return 0;}