Vexoben
Jun 18, 2018
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4033
（刷新以获取数学公式）
题意
有一棵点数为\(N\)的树，树边有边权。给你一个在\(0\)~\(N\)之内的正整数\(K\)，你要在这棵树中选择\(K\)个点，将其染成黑色，并将其他的\(N-K\)个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。
\[N,K<=2000\]题解
对于一条边，假设去掉它后分成的两个联通块中，黑色节点个数分别为\(b_1,b_2\)，白色节点个数分别为\(w_1,w_2\)，则定义它的贡献\(con=weight*(b_1*b_2+w_1*w_2)\)
定义状态\(f[i][j]\)表示以\(i\)为根的子树，有\(j\)个点被染成黑色，子树内的边产生的最大贡献和。
转移的时候，将节点\(x\)的子树一个个加入。设\(y\)是当前转移到的儿子，转移方程是：
\[f[x][i]=max(f[x][i],max(f[x][j]+f[y][i-j]+con(x,y)))\]其中\(con(x,y)\)是边\((x,y)\)产生的贡献，它的值为:
\[weight(x,y)*((i-j)*(K-i+j)+(size[y]-i+j)*(n-m-size[y]+i-j))\]这样复杂度看起来是\(O(n^3)\)的。但是我们分析一下会发现复杂度为:
.JPG)
对于点对\((u,v)\)，仅在\(x=LCA(u,v)\)的时候对答案有贡献，从而复杂度是\(O(n^2)\)的。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2050;
int n,m,E;
int fa[N],siz[N],fir[N],nex[N<<1],arr[N<<1];
LL g[N],len[N<<1],f[N][N];
inline void Add_Edge(int x,int y,LL l) {
nex[++E]=fir[x];
fir[x]=E; arr[E]=y; len[E]=l;
}
void dfs(int x) {
siz[x]=1;
for (int i=fir[x];i;i=nex[i]) {
if (arr[i]==fa[x]) continue;
fa[arr[i]]=x; dfs(arr[i]);
int sx=min(m,siz[x]);
int sy=min(m,siz[arr[i]]);
memset(g,0,sizeof(LL)*(m+1));
for (LL j=0;j<=sx;j++)
for (LL k=0;k<=sy;k++) {
if (j+k>m) break;
LL eval=len[i]*(k*(m-k)+(siz[arr[i]]-k)*(n-m-siz[arr[i]]+k));
g[j+k]=max(g[j+k],f[x][j]+f[arr[i]][k]+eval);
}
for (int j=0;j<=m;j++) f[x][j]=g[j];
siz[x]+=siz[arr[i]];
}
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++) {
int x,y; LL l; scanf("%d%d%lld",&x,&y,&l);
Add_Edge(x,y,l); Add_Edge(y,x,l);
}
dfs(1);
printf("%lld",f[1][m]);
return 0;
}