https://www.zybuluo.com/ysner/note/1300088
题面
有一棵\(n\)个点的树，现在在上面放\(k\)个标记，使得每个点的权值乘上自己到最近的标记祖先的距离的和最小。
- \(n\leq100,k\leq50\)
解析
神仙题。
神仙之处在于只能向祖先转移。
状态中要有表示自己最近标记祖先的距离的量。
再加上要有表示标记数的量。
因此状态也就呼之欲出了，设\(f[i][j][k]\)表示\(i\)号点，自己的最近标记祖先为\(j\)，子树中有\(k\)个标记的答案。
默认\(f\)数组表示当前点不打标记，\(g\)数组表示当前点打标记。
那么这样就可以转移了。
- 合并子节点与当前结点中最近标记祖先相同的状态。（\(0\)标记的继承到所有标记数状态中）
- 枚举子节点状态数，最小化当前结点最近标记祖先的状态。
- \(f\)数组加上代价。
自己完全想不出系列。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=105;
int n,K,d[N],h[N],cnt,s[N],sta[N],top,f[N][N][55],g[N][N][55];
struct Edge{int to,nxt,w;}e[N];
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int min(re int x,re int y){return x<y?x:y;}
il void dfs(re int u)
{
sta[++top]=u;
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
d[v]=d[u]+e[i].w;
dfs(v);
fp(j,1,top)
fq(k,K,0)
{
f[u][sta[j]][k]+=f[v][sta[j]][0];
g[u][sta[j]][k]+=f[v][u][0];
fq(x,k,0)
{
f[u][sta[j]][k]=min(f[u][sta[j]][k],f[u][sta[j]][k-x]+f[v][sta[j]][x]);
g[u][sta[j]][k]=min(g[u][sta[j]][k],g[u][sta[j]][k-x]+f[v][u][x]);
}
}
}
fp(j,1,top)
fq(k,K,0)
if(k) f[u][sta[j]][k]=min(g[u][sta[j]][k-1],f[u][sta[j]][k]+s[u]*(d[u]-d[sta[j]]));
else f[u][sta[j]][k]+=s[u]*(d[u]-d[sta[j]]);
--top;
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();K=gi();
fp(i,1,n)
{
s[i]=gi();re int u=gi(),w=gi();
add(u,i,w);
}
dfs(0);
printf("%d\n",f[0][0][K]);
return 0;
}