[IOI2005]Riv 河流

DP 树形DP

题面

有一棵$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;
}