路径规划

#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005],c[100005];
int cnt[100005];
long long f[100005][105][2],g[105][2],len[100005];
int w[105];
int n,m;
void dp(int n1,int fa)
{
	if(a[n1].size()==1&&n1!=1)
	{
		cnt[n1]=1;
	}
	f[n1][0][0]=f[n1][0][1]=0;
	for(int i=0;i<a[n1].size();i++)
	{
		if(a[n1][i]!=fa)
		{
			int k=a[n1][i];
			dp(k,n1);
			cnt[n1]+=cnt[a[n1][i]];
			memcpy(g,f[n1],sizeof(f[n1]));
			len[n1]=max(len[n1],len[a[n1][i]]+c[n1][i]);
			f[n1][0][1]=f[n1][0][1]+f[a[n1][i]][0][1]+2*c[n1][i];
			f[n1][0][0]=f[n1][0][1]-len[n1];
			for(int j=1;j<min(cnt[n1],m+1);j++)
			{
				f[n1][j][0]=min(g[j][1]+f[k][0][0]+c[n1][i],g[j][0]+f[k][0][1]+2*c[n1][i]);
				f[n1][j][0]=min(f[n1][j][0],g[j-1][0]+f[k][0][0]+c[n1][i]);
				for(int l=1;l<=cnt[k];l++)
				{
					if(j-l<0)
					{
						break;
					}
					if(l<cnt[k])
					{
						f[n1][j][0]=min(f[n1][j][0],g[j-l][1]+f[k][l][0]+c[n1][i]);
					}
					f[n1][j][0]=min(f[n1][j][0],g[j-l][0]+f[k][l][1]+2*c[n1][i]);
				}
			}
			for(int j=1;j<=min(cnt[n1],m);j++)
			{
				f[n1][j][1]=g[j][1]+f[k][0][1]+2*c[n1][i];
				f[n1][j][1]=min(f[n1][j][1],g[j-1][0]+f[k][0][0]+c[n1][i]);
				for(int l=1;l<=cnt[k];l++)
				{
					if(j-l<0)
					{
						break;
					}
					f[n1][j][1]=min(f[n1][j][1],g[j-l][1]+f[k][l][1]+2*c[n1][i]);
					if(j-l-1>=0)
					{
						f[n1][j][1]=min(f[n1][j][1],g[j-l-1][0]+f[k][l][0]+c[n1][i]);
					}
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(f,0x3f,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u].push_back(v);
		a[v].push_back(u);
		c[u].push_back(w);
		c[v].push_back(w);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>w[i];
	}
	dp(1,0);
	sort(w+1,w+m+1);
	int cur=0;
	long long ans=INT_MAX;
	for(int i=0;i<=min(m,cnt[1]);i++)
	{
		ans=min(ans,f[1][i][1]+cur);
		cur+=w[i+1];
	}
	cout<<ans<<endl;
	return 0;
}