{"problem":{"name":"BZOJ3252 攻略","description":{"content":"给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10641"},"statements":[{"statement_type":"Markdown","content":"给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。\n\n## Input\n\n第一行两个正整数 $n,k$。\n\n第二行输入 $n$ 个正整数 $w_i$，表示每个结点的点权。\n\n接下来输入 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示结点 $u$ 是结点 $v$ 的父亲。\n\n## Output\n\n输出一个正整数，表示答案。\n\n[samples]\n\n## Background\n\n众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略 $k$ 部游戏。\n\n今天他得到了一款新游戏《XX 半岛》，这款游戏有 $n$ 个场景，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略 $k$ 次该游戏，问他观赏到的场景的价值和最大是多少？（同一场景观看多次是不能重复得到价值的）\n\n>“为什么你还没玩就知道每个场景的价值呢？”  \n>“我已经看到结局了。”\n\n## Note\n\n对于所有数据，保证 $1\\leq n\\leq 2\\times 10^5$，$1\\leq w_i\\leq 2^{31}-1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10641","tags":["贪心","线段树","O2优化","可并堆","树链剖分"],"sample_group":[["5 2\n4 3 2 1 1\n1 2\n1 5\n2 3\n2 4","10"]],"created_at":"2026-03-03 11:09:25"}}