题目链接
http://118.190.20.162/view.page?gpid=T90
解题思路
考虑DP，F[i][j]表示i子树中选j个点的代价，注意到某个子树与父亲相连的边的代价只与子树选的点个数有关，可以在转移时对每条边计算代价。 DP转移： F[i][j]=min{F[i][j-k]+F[son][k]+k
∗
\ast
∗(K-k)
∗
\ast
∗c}，k为子树选取点个数，c为边代价。 时间复杂度O(NK^2)
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=50010;
const long long INF=1LL<<60;
int tot,head[MAXN];
struct Edge {int to,net,v;}E[MAXN<<1];
void addedge(int x,int y,int v)
{
E[++tot].to=y;E[tot].net=head[x];head[x]=tot;E[tot].v=v;
E[++tot].to=x;E[tot].net=head[y];head[y]=tot;E[tot].v=v;
}
int N,M,K,fa[MAXN],size[MAXN];long long F[MAXN][210];bool Mark[MAXN];
void dfs(int x)
{
for (int i=1;i<=K;++i) F[x][i]=INF;
if (Mark[x]) size[x]=1,F[x][1]=0;
for (int i=head[x];i;i=E[i].net)
if (E[i].to!=fa[x])
{
fa[E[i].to]=x;
dfs(E[i].to);
size[x]+=size[E[i].to];
for (int j=min(K,size[x]);j;--j)
{
int v=min(size[E[i].to],min(K,j));
for (int k=1;k<=v;++k)
F[x][j]=min(F[x][j],F[x][j-k]+F[E[i].to][k]+1LL*(K-k)*k*E[i].v);
}
}
}
int main()
{
cin>>N>>M>>K;
for (int i=1;i<=M;++i)
{
int x;
scanf("%d",&x);
Mark[x]=true;
}
for (int i=1;i<N;++i)
{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
addedge(x,y,v);
}
dfs(1);
cout<<F[1][K]<<endl;
return 0;
}
