[COCI 2021/2022 #4] Parkovi

Luogu

IDLGP8314

Time3000ms

Memory500MB

DifficultyP6

2021Special JudgeCOCI（克罗地亚）

这个城市由 $n$ 个社区组成，社区间由 $n-1$ 条道路连接。并且从任意一个社区出发，可以到任意一个社区去。一共会建造 $k$ 座公园，同一个社区内只会存在一座公园。市政府希望尽可能减小从每个社区到最近公园的距离的最大值。帮助政府应该在那些社区建造公园，可以使每个社区到最近公园的距离的最大值最小。 ## Input 第一行包含两个整数 $n,k$，分别表示社区数目和需要建造的公园数目。接下来 $n-1$ 行，第 $i$ 行包含三个数 $a_i,b_i,w_i$，分别表示有一条长度为 $w_i$ 道路连接着社区 $a_i,b_i$。 ## Output 第一行包含一个整数，即每个社区到最近公园的距离的最大值的最小值。第二行包含 $k$ 个整数，可以使每个社区到最近公园的距离的最大值最小所需要修建的公园所在的社区编号。 **如果有多组解输出一组解。** [samples] ## Background 市政府决定修建公园来美化景观。为了让公园不仅好看，而且有用。市政府为了市民的幸福，希望公园里居民们更近一些。 ## Note **【样例 3 解释】** 如果只在 $3,4$ 号社区建公园，最大距离不会改变。但是市政府想建 $k$ 个公园，所以需要在其他地方再建两个。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - Subtask 1（10 pts）：$1 ≤ n ≤ 20$。 - Subtask 2（10 pts）：$k=1$。 - Subtask 3（30 pts）：$\forall i\in\{1,2,3,\dots,n-1\},a_i=i,b_i=i+1$。 - Subtask 4（60 pts）：没有额外限制。对于 $100\%$ 的数据，$1\le k\le n\le2\times10^5,1\le a_i,b_i\le n,1\le w_i \le 1e9$。 **【提示与说明】** **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T4 Parkovi。**

Samples

Input #1

Output #1

8
4 5 8

Input #2

Output #2

3
2 4

Input #3

Output #3

1
3 4 1 2

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #4] Parkovi",
    "description": {
      "content": "这个城市由 $n$ 个社区组成，社区间由 $n-1$ 条道路连接。并且从任意一个社区出发，可以到任意一个社区去。一共会建造 $k$ 座公园，同一个社区内只会存在一座公园。市政府希望尽可能减小从每个社区到最近公园的距离的最大值。 帮助政府应该在那些社区建造公园，可以使每个社区到最近公园的距离的最大值最小。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 512000
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8314"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这个城市由 $n$ 个社区组成，社区间由 $n-1$ 条道路连接。并且从任意一个社区出发，可以到任意一个社区去。一共会建造 $k$ 座公园，同一个社区内只会存在一座公园。市政府希望尽可能减小从每个社区到最近公园的距离的最大值。\n\n帮助政府应该在那些社区建造公园，可以使每个社区到最近公园的距离的最大值最小。\n\n## Input\n\n第一行包含两个整数 $n,k$，分别表示社区数目和需要建造的公园数目。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments