BZOJ3252 攻略

Luogu

IDLGP10641

Time1000ms

Memory512MB

DifficultyP5

贪心线段树O2优化可并堆树链剖分

给定一个有 $n$ 个结点的树，树有点权且点权为正整数。现选取 $k$ 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。 ## Input 第一行两个正整数 $n,k$。第二行输入 $n$ 个正整数 $w_i$，表示每个结点的点权。接下来输入 $n-1$ 行，每行 $2$ 个正整数 $u,v$，表示结点 $u$ 是结点 $v$ 的父亲。 ## Output 输出一个正整数，表示答案。 [samples] ## Background 众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略 $k$ 部游戏。今天他得到了一款新游戏《XX 半岛》，这款游戏有 $n$ 个场景，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同时攻略 $k$ 次该游戏，问他观赏到的场景的价值和最大是多少？（同一场景观看多次是不能重复得到价值的） >“为什么你还没玩就知道每个场景的价值呢？” >“我已经看到结局了。” ## Note 对于所有数据，保证 $1\leq n\leq 2\times 10^5$，$1\leq w_i\leq 2^{31}-1$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "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## Out...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments