题目：
虽说是几个月前曾经讲过的题，但没有题解而自己(花了两个多小时)A了好高兴！！！
这是一个很好的套路：“承诺”以算值。
伐木场放在哪里对于节点的值是有影响的，所以自然的思路就是把和该节点有关的伐木场位置也压进状态里，对于不同的状态算出不同的值；
也就是“承诺”那些伐木场会放在哪里。
相同的承诺之间才能转移。
这样就有了一个问题：该节点的“承诺”记录的是该节点上方的下一个伐木场在哪；但是该节点放不放伐木场对于转移也有影响。
试图用“承诺下一个伐木场在0”表示该节点放伐木场，但是有诸多不对劲；比如根据定义，0处承诺了的话，上面就没有“下一个伐木场的位置”了，导致无法转移之类；
然后终于想到可以再开一维状态0/1表示该节点到底放没放伐木场！这样一下就变得通顺又简单！
树形DP的坑点：那个 j 的倒序！仔细一看转移需要用到同层的小一些的 j 的。
还有常规的看看siz等等。
#include#include #include #define ll long longusing namespace std;const int N=105;const ll INF=0x7fffffff;int n,m,head[N],fa[N],xnt,siz[N],len[N];ll a[N],c[N][N],ed[N],dp[N][55][N][2];struct Edge{ int next,to;ll w; Edge(int n=0,int t=0,ll w=0):next(n),to(t),w(w) {}}edge[N<<1];void init(int cr,ll dis,int cnt,int nw){ c[cr][cnt]=dis*a[cr];if(cnt)dp[cr][0][cnt][0]=c[cr][cnt]; if(!nw) { len[cr]=cnt;return; } init(cr,dis+ed[nw],cnt+1,fa[nw]);}void dfs(int cr){ siz[cr]=1;for(int j=1;j<=n;j++)dp[cr][j][0][1]=0; for(int k=1;k<=len[cr];k++)dp[cr][1][k][1]=0; for(int i=head[cr],v;i;i=edge[i].next) { dfs(v=edge[i].to); for(int j=min(m,siz[cr]+siz[v]);j>=0;j--)// { for(int k=0;k<=len[cr];k++) { dp[cr][j][k][1]+=min(dp[v][0][1][0],dp[v][0][1][1]); dp[cr][j][k][0]+=min(dp[v][0][k+1][0],dp[v][0][k+1][1]);// printf("dp[%d][%d][%d]=%lld dp[%d][%d][%d]=%lld\n"// ,cr,j,k,dp[cr][j][k],v,0,k+1,dp[v][0][k+1]); for(int l=max(1,j-siz[cr]);l<=j&&l<=siz[v];l++) dp[cr][j][k][0]=min(dp[cr][j][k][0],dp[cr][j-l][k][0]+min(dp[v][l][k+1][0],dp[v][l][k+1][1])), dp[cr][j][k][1]=min(dp[cr][j][k][1],dp[cr][j-l][k][1]+min(dp[v][l][1][0],dp[v][l][1][1]));// printf("dp[%d][%d][%d][0]=%lld dp[%d][%d][%d][0]=%lld\ndp[%d][%d][%d][0]=%lld dp[%d][%d][%d][1]=%lld\n"// ,cr,j,k,dp[cr][j][k][0],cr,j-l,k,dp[cr][j-l][k][0],v,l,k+1,dp[v][l][k+1][0],v,l,k+1,dp[v][l][k+1][1]),// printf("dp[%d][%d][%d][1]=%lld dp[%d][%d][%d][1]=%lld\ndp[%d][%d][%d][0]=%lld dp[%d][%d][%d][1]=%lld\n\n"// ,cr,j,k,dp[cr][j][k][1],cr,j-l,k,dp[cr][j-l][k][1],v,l,k+1,dp[v][l][k+1][0],v,l,k+1,dp[v][l][k+1][1]); } } siz[cr]+=siz[v]; }}int main(){ scanf("%d%d",&n,&m);int x;ll z; for(int i=1;i<=n;i++) { scanf("%lld%d%lld",&a[i],&x,&z); edge[++xnt]=Edge(head[x],i,z);head[x]=xnt; fa[i]=x;ed[i]=z; } memset(dp,1,sizeof dp);dp[0][0][0][0]=0; for(int i=1;i<=n;i++)init(i,0,0,i); dfs(0); printf("%lld",dp[0][m][0][0]); return 0;}