标签：收集 int 4005 back 签名 push n1 dp
- 虽然这道题看起来好像不太能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;
}
标签：收集,
int,
4005,
back,
签名,
push,
n1,
dp
From： https://www.cnblogs.com/watersail/p/18382407