E. Information Reform

Codeforces

IDCF70E

Time2000ms

Memory256MB

Difficulty—

dpimplementationtrees

English · Original

Chinese · Translation

Formal · Original

Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built so that it is possible to get to any city from any other one in exactly one way, and the roads' lengths are equal. The North Pole governor decided to carry out an information reform. Several cities were decided to be chosen and made regional centers. Maintaining a region center takes _k_ fishlars (which is a local currency) per year. It is assumed that a regional center always has information on the latest news. For every city which is not a regional center, it was decided to appoint a regional center which will be responsible for keeping this city informed. In that case the maintenance costs will be equal to _d__len_ fishlars per year, where _len_ is the distance from a city to the corresponding regional center, measured in the number of roads along which one needs to go. Your task is to minimize the costs to carry out the reform. ## Input The first line contains two given numbers _n_ and _k_ (1 ≤ _n_ ≤ 180, 1 ≤ _k_ ≤ 105). The second line contains _n_ - 1 integers _d__i_, numbered starting with 1 (_d__i_ ≤ _d__i_ + 1, 0 ≤ _d__i_ ≤ 105). Next _n_ - 1 lines contain the pairs of cities connected by a road. ## Output On the first line print the minimum number of fishlars needed for a year's maintenance. On the second line print _n_ numbers, where the _i_\-th number will represent the number of the regional center, appointed to the _i_\-th city. If the _i_\-th city is a regional center itself, then you should print number _i_. If there are several solutions to that problem, print any of them. [samples]

尽管已经进入二十一世纪，但在海象国，大众媒体并不十分普及。城市之间的消息只能通过沿道路旅行的信使传递。海象国的道路网络设计使得任意两座城市之间恰好存在唯一一条路径，且所有道路的长度相等。北极总督决定实施一项信息改革。决定选择若干城市作为地区中心。维持一个地区中心每年需要花费 #cf_span[k] 鱼拉尔（当地货币）。假设每个地区中心始终掌握最新消息。对于每一个非地区中心的城市，将指定一个地区中心负责向其传递信息。此时，维护成本为每年 #cf_span[dlen] 鱼拉尔，其中 #cf_span[len] 表示该城市到对应地区中心的距离，即需要经过的道路数量。你的任务是最小化实施改革所需的总成本。第一行包含两个给定数字 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 180, 1 ≤ k ≤ 105]）。第二行包含 #cf_span[n - 1] 个整数 #cf_span[di]，编号从 1 开始（#cf_span[di ≤ di + 1, 0 ≤ di ≤ 105]）。接下来的 #cf_span[n - 1] 行每行包含一对由道路连接的城市。第一行输出维持一年所需最少的鱼拉尔数。第二行输出 #cf_span[n] 个数字，其中第 #cf_span[i] 个数字表示分配给第 #cf_span[i] 座城市的地区中心编号。如果第 #cf_span[i] 座城市本身就是地区中心，则应输出数字 #cf_span[i]。如果存在多个可行解，输出任意一个即可。 ## Input 第一行包含两个给定数字 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 180, 1 ≤ k ≤ 105]）。第二行包含 #cf_span[n - 1] 个整数 #cf_span[di]，编号从 1 开始（#cf_span[di ≤ di + 1, 0 ≤ di ≤ 105]）。接下来的 #cf_span[n - 1] 行每行包含一对由道路连接的城市。 ## Output 第一行输出维持一年所需最少的鱼拉尔数。第二行输出 #cf_span[n] 个数字，其中第 #cf_span[i] 个数字表示分配给第 #cf_span[i] 座城市的地区中心编号。如果第 #cf_span[i] 座城市本身就是地区中心，则应输出数字 #cf_span[i]。如果存在多个可行解，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of cities. Let $ k \in \mathbb{Z}^+ $ be the number of regional centers to be chosen. Let $ T = (V, E) $ be a tree with $ |V| = n $, where each edge has unit length. Let $ c \in \mathbb{R}^+ $ be the cost per year to maintain a regional center. Let $ d(u, v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $ in $ T $. **Constraints** 1. $ 1 \leq n \leq 180 $ 2. $ 1 \leq k \leq 10^5 $ 3. The graph $ T $ is a tree. 4. Exactly $ k $ vertices must be selected as regional centers. 5. Each non-center city must be assigned to exactly one regional center (its nearest, in case of ties, any may be chosen). **Objective** Minimize the total annual cost: $$ \min_{S \subseteq V,\, |S| = k} \left( c \cdot |S| + \sum_{v \in V \setminus S} d(v, \text{nearest}(v, S)) \right) $$ where $ \text{nearest}(v, S) = \arg\min_{u \in S} d(v, u) $. **Output Requirements** 1. The minimal total cost. 2. An assignment function $ f: V \to S $ such that $ f(v) = v $ if $ v \in S $, and $ f(v) \in S $ is a nearest regional center to $ v $ otherwise.

Samples

Input #1

8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5

Output #1

38
3 3 3 4 3 4 3 3

API Response (JSON)

{
  "problem": {
    "name": "E. Information Reform",
    "description": {
      "content": "Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF70E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "尽管已经进入二十一世纪，但在海象国，大众媒体并不十分普及。城市之间的消息只能通过沿道路旅行的信使传递。海象国的道路网络设计使得任意两座城市之间恰好存在唯一一条路径，且所有道路的长度相等。\n\n北极总督决定实施一项信息改革。决定选择若干城市作为地区中心。维持一个地区中心每年需要花费 #cf_span[k] 鱼拉尔（当地货币）。假设每个地区中心始终掌握最新消息。\n\n对于每一个非地区中心的城市，将指定一个...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of regional centers to be chosen.  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments