思路不算很难，但细节处理很麻烦
前面建图、多叉转二叉，以及确定dp处理序列的过程都是套路，dp的状态转移过程以注释的形式阐述
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int N,M,K;
struct Edge
{
int to,next;
int weight;
void assign(int t,int n,int w)
{
to=t; next=n; weight=w;
}
};
Edge elist[];
];
];
][]; //0 is left and 1 is right
];
int ecnt;
void initE()
{
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
memset(child,-,sizeof(child));
weight[]=;
ecnt=;
}
inline void addEdge(int from,int to,int weight)
{
elist[ecnt].assign(to,head[from],weight);
head[from]=ecnt++;
elist[ecnt].assign(from,head[to],weight);
head[to]=ecnt++;
}
bool input()
{
scanf("%d%d%d",&N,&M,&K);
bool ok=true;
>N) ok=false; //输出-1的情况
initE();
int a,b,c;
;i<N;i++)
{
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
}
return ok;
}
void buildBinaryTree(int cur)
{
vis[cur]=true;
;
;e=elist[e].next)
{
int& to=elist[e].to;
int& w=elist[e].weight;
if(!vis[to])
{
weight[to]=w;
)
child[cur][]=to;
else
child[last][]=to;
last=to;
buildBinaryTree(to);
}
}
}
][][];
/*
dp[n][m][k]：处理到第n个节点时，大头已经吃掉了m个果子，其父节点将被（k=1）或不被（k=0）大头吃，此情况下的最优值
dp[n]的处理范围：孩子兄弟二叉树中，以节点n为根的子树
dp的初值见下方代码，ans=dp[v][K-1][1]，v为孩子兄弟二叉树中1号节点的左孩子
*/
std::queue<int> seq;
void getSeq(int cur)
{
]!=-) getSeq(child[cur][]);
]!=-) getSeq(child[cur][]);
seq.push(cur);
} //先处理右孩子，再处理左孩子，最后处理自身
/*
M>=3时，小头的总难受值的最小值必为0
取两个小头A和B，奇数层的果子由A吃，偶数层的果子由B吃，这样难受值必为0
所以只需考虑大头的难受值
*/
int solve_aux_3()
//若无特殊说明：solve_aux函数注释中提到的有关树的概念均指孩子兄弟二叉树，opt代指当前决策的较优值，“不吃”和“吃”均指大头
{
int ans;
while(!seq.empty())
{
int cur=seq.front();
seq.pop();
);
]!=-) st|=;
]!=-) st|=;
) //cur是叶子节点
{
dp[cur][][]=dp[cur][][]=;
dp[cur][][]=;
dp[cur][][]=weight[cur];
}
) //只有右孩子，状态转移和线性dp类似
{
];
dp[cur][][]=;
;i<K;i++)
dp[cur][i][]=std::min(dp[rc][i][],dp[rc][i-][]); //对于当前果子，opt=min（不吃，吃）
dp[cur][][]=;
;i<K;i++)
dp[cur][i][]=std::min(dp[rc][i][],dp[rc][i-][]+weight[cur]); //opt=min（不吃，吃）
}
) //只有左孩子
{
];
) ans=dp[lc][K-][]; //最终答案
else
{
dp[cur][][]=dp[cur][][]=;
;i<K;i++)
dp[cur][i][]=std::min(dp[lc][i][],dp[lc][i-][]); //opt=min（不吃，吃）
;i<K;i++)
dp[cur][i][]=std::min(dp[lc][i][],dp[lc][i-][]+weight[cur]); //opt=min（不吃，吃）
}
}
else //st=3，既有左孩子又有右孩子，最复杂的情况
{
];
];
dp[cur][][]=dp[cur][][]=;
;i<K;i++) //dp[cur][i][0]
{
;j<=i;j++) //不吃当前的果子
dp[cur][i][]=std::min(dp[lc][j][]+dp[rc][i-j][],dp[cur][i][]); //分配i，取最优的分配方案
;j<i;j++) //吃当前的果子
dp[cur][i][]=std::min(dp[lc][j][]+dp[rc][i-j-][],dp[cur][i][]);
}
;i<K;i++) //dp[cur][i][1]
{
;j<=i;j++) //不吃
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j][]);
;j<i;j++) //吃
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j-][]+weight[cur]);
}
}
}
return ans;
}
/*
M=2时的dp方程与M>2时形式类似，但细节上有所不同（包括初值的设置和状态转移）
此时大头和小头的难受值必须同时考虑
*/
int solve_aux_2()
{
int ans;
while(!seq.empty())
{
int cur=seq.front();
seq.pop();
);
]!=-) st|=;
]!=-) st|=;
)
{
dp[cur][][]=dp[cur][][]=;
dp[cur][][]=dp[cur][][]=weight[cur]; //注意这里赋初值的差异
//dp[cur][0][0]表示原树中当前节点和父节点的果子都由小头吃，所以该段树枝的难受值也必须考虑
//类似的差异会在下方用“！”标注，请读者自行体会
}
)
{
];
dp[cur][][]=dp[rc][][];
dp[cur][][]=dp[rc][][]+weight[cur]; //！
;i<K;i++)
{
dp[cur][i][]=std::min(dp[rc][i][]+weight[cur],dp[rc][i-][]); //！
dp[cur][i][]=std::min(dp[rc][i][],dp[rc][i-][]+weight[cur]);
}
}
)
{
];
) ans=dp[lc][K-][];
else
{
dp[cur][][]=dp[lc][][]; //！
dp[cur][][]=dp[lc][][]+weight[cur];
;i<K;i++)
{
dp[cur][i][]=std::min(dp[lc][i][]+weight[cur],dp[lc][i-][]); //！
dp[cur][i][]=std::min(dp[lc][i][],dp[lc][i-][]+weight[cur]);
}
}
}
else
{
];
];
dp[cur][][]=dp[lc][][]+dp[rc][][]; //！
dp[cur][][]=dp[lc][][]+dp[rc][][]+weight[cur];
;i<K;i++)
{
;j<=i;j++)
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j][]+weight[cur]); //！
;j<i;j++)
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j-][]);
;j<=i;j++)
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j][]);
;j<i;j++)
dp[cur][i][]=std::min(dp[cur][i][],dp[lc][j][]+dp[rc][i-j-][]+weight[cur]);
}
}
}
return ans;
}
int solve()
{
memset(dp,0x3f,sizeof(dp));
buildBinaryTree();
getSeq();
?solve_aux_2():solve_aux_3();
}
int main()
{
if(!input()) printf("-1");
else printf("%d",solve());
;
}