1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 50005
#define K 105
typedef long long int ll;
struct edge {int v,w;};
int imp[N];std::vector<edge> edges[N];
int n,k;ll f[N][K];
void dfs(int x,int fa) {
for(int i=0,sz=edges[x].size();i<sz;++i) {
edge e=edges[x][i];if(e.v==fa) continue;dfs(e.v,x);
for(int j=k;j>0;--j) {
for(int kk=j;kk>=0;--kk) {
if(kk) f[x][j]=std::min(f[x][j],f[e.v][kk]+f[x][j-kk]+((k-kk)?(ll)e.w*kk*(k-kk):0));
if(imp[e.v]&&j>kk) {
f[x][j]=std::min(f[x][j],f[e.v][kk]+f[x][j-kk-1]+(ll)e.w*(kk+1)*(k-kk-1));
}
}
}
}
}
int main() {
int m;scanf("%d%d%d",&n,&m,&k);
while(m--) {int t;scanf("%d",&t);imp[t]=true;}
for(int i=1;i<n;++i) {
int a,b,c;scanf("%d%d%d",&a,&b,&c);
edges[a].push_back((edge){b,c});
edges[b].push_back((edge){a,c});
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i) f[i][0]=0;
dfs(1,0);ll ans=f[1][k];if(imp[1]&&k) ans=std::min(ans,f[1][k-1]);
printf("%lld\n",ans);
return 0;
}
|