收集签名

watersail / 2024-08-27 / 原文

虽然这道题看起来好像不太能DP的样子，但事实上的确是树形DP，我们考虑每条边怎样被覆盖——而不是被整条路径局限了思维
我们依次用x的每个子树y更新x，在子树中枚举i，i>0时，|i|表示有多少个“超级技能”起点向外扩展，i<0时，|i|表示有多少个“超级技能”起点向内扩展，同时子树内有|i|个“超级技能”终点被处理
那么这条边就要被技能覆盖k次，产生i*k的代价
同时，除非i=-lefy，否则这条边依然要被正常地走一次，产生w(x,y)的代价
原子树的代价为dp[x][s-i]
子树内其他边的代价为dp[y][i]，因为i>0时，要有|i|个未处理的“超级技能”起点，才能向外扩展；i<0时，要有|i|个未处理的“超级技能”终点，才能向内扩展
通过将dp的下标扩展到负数，统一“起点”“终点”两种情况
对于一棵子树，在子树内的代价已经被计算的前提下，我们并不关心起点/终点的具体位置，而只关心里面有多少个起点/终点

点击查看代码

#include <bits/stdc++.h>
using namespace std;
vector<int>a[4005],c[4005];
int n;
long long k;
int fa[4005],s[4005],h[4005];
bool b[4005];
void dfs(int n1)
{
	if(n1!=1&&a[n1].size()==1)
	{
		h[n1]=1;
	}
	else
	{
		h[n1]=0;
	}
	s[n1]=b[n1];
	for(int i=0;i<a[n1].size();i++)
	{
		if(a[n1][i]!=fa[n1])
		{
			fa[a[n1][i]]=n1;
			dfs(a[n1][i]);
			s[n1]+=s[a[n1][i]];
			h[n1]+=h[a[n1][i]];
		}
	}
}
long long f[4005][8005];
void dp(int n1)
{
	for(int j=-h[n1];j<=s[n1];j++)
	{
		f[n1][j+h[n1]]=-1;
	}
	if(n1!=1&&a[n1].size()==1)
	{
		f[n1][-1+h[n1]]=0;
	}
	f[n1][h[n1]]=0;
	if(b[n1])
	{
		f[n1][1+h[n1]]=0;
	}
	for(int i=0;i<a[n1].size();i++)
	{
		if(a[n1][i]!=fa[n1])
		{
			int y=a[n1][i];
			dp(y);
			for(int j=-h[n1];j<=s[n1];j++)
			{
				f[0][j+h[n1]]=f[n1][j+h[n1]];
				f[n1][j+h[n1]]=-1;
			}
			for(int l=-h[y];l<=s[y];l++)
			{
				if(f[y][l+h[y]]!=-1)
				{
					for(int j=-h[n1];j<=s[n1];j++)
					{
						if(j-l>=-h[n1]&&j-l<=s[n1]&&f[0][j-l+h[n1]]!=-1)
						{
							long long val=abs(l)*k+(l>-h[y])*c[n1][i]+f[0][j-l+h[n1]]+f[y][l+h[y]];
							if(f[n1][j+h[n1]]==-1)
							{
								f[n1][j+h[n1]]=val; 
							} 
							else
							{
								f[n1][j+h[n1]]=min(f[n1][j+h[n1]],val);
							}
						}
					}
				}
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			a[i].clear();
			c[i].clear();
			int opt;
			cin>>opt;
			b[i]=opt;
			fa[i]=0;
		}
		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);
		}
		dfs(1);
		dp(1);
		cout<<2*f[1][h[1]]<<endl;
	}
	return 0;
}