C. Beavermuncher-0xFF

Codeforces

IDCF77C

Time3000ms

Memory256MB

Difficulty—

dfs and similardpdsugreedytrees

English · Original

Chinese · Translation

Formal · Original

_"Eat a beaver, save a tree!" — That will be the motto of ecologists' urgent meeting in Beaverley Hills._ _And the whole point is that the population of beavers on the Earth has reached incredible sizes! Each day their number increases in several times and they don't even realize how much their unhealthy obsession with trees harms the nature and the humankind. The amount of oxygen in the atmosphere has dropped to 17 per cent and, as the best minds of the world think, that is not the end._ _In the middle of the 50-s of the previous century a group of soviet scientists succeed in foreseeing the situation with beavers and worked out a secret technology to clean territory. The technology bears a mysterious title "Beavermuncher-0xFF". Now the fate of the planet lies on the fragile shoulders of a small group of people who has dedicated their lives to science._ _The prototype is ready, you now need to urgently carry out its experiments in practice._ You are given a tree, completely occupied by beavers. A tree is a connected undirected graph without cycles. The tree consists of _n_ vertices, the _i_\-th vertex contains _k__i_ beavers. "Beavermuncher-0xFF" works by the following principle: being at some vertex _u_, it can go to the vertex _v_, if they are connected by an edge, and eat **exactly one** beaver located at the vertex _v_. It is impossible to move to the vertex _v_ if there are no beavers left in _v_. "Beavermuncher-0xFF" **cannot** just stand at some vertex and eat beavers in it. "Beavermuncher-0xFF" must move without stops. Why does the "Beavermuncher-0xFF" works like this? Because the developers have not provided place for the battery in it and eating beavers is necessary for converting their mass into pure energy. It is guaranteed that the beavers will be shocked by what is happening, which is why they will not be able to move from a vertex of the tree to another one. As for the "Beavermuncher-0xFF", it can move along each edge in both directions while conditions described above are fulfilled. The root of the tree is located at the vertex _s_. This means that the "Beavermuncher-0xFF" begins its mission at the vertex _s_ and it must return there at the end of experiment, because no one is going to take it down from a high place. Determine the maximum number of beavers "Beavermuncher-0xFF" can eat and return to the starting vertex. ## Input The first line contains integer _n_ — the number of vertices in the tree (1 ≤ _n_ ≤ 105). The second line contains _n_ integers _k__i_ (1 ≤ _k__i_ ≤ 105) — amounts of beavers on corresponding vertices. Following _n_ - 1 lines describe the tree. Each line contains two integers separated by space. These integers represent two vertices connected by an edge. Vertices are numbered from 1 to _n_. The last line contains integer _s_ — the number of the starting vertex (1 ≤ _s_ ≤ _n_). ## Output Print the maximum number of beavers munched by the "Beavermuncher-0xFF". Please, do not use _%lld_ specificator to write 64-bit integers in C++. It is preferred to use _cout_ (also you may use _%I64d_). [samples]

_"吃掉海狸，拯救树木！"——这是比弗利山生态学家紧急会议的口号。_ _而问题的症结在于，地球上海狸的数量已经达到了惊人的规模！每天它们的数量都会增加数倍，却丝毫没有意识到自己对树木的病态痴迷如何危害自然与人类。大气中的氧气含量已降至17%，而世界顶尖学者认为，这还远非终点。_ _在上世纪50年代中期，一群苏联科学家成功预见了海狸的危机，并研发出一项秘密技术来清理领土。这项技术拥有一个神秘的名称：“Beavermuncher-0xFF”。如今，地球的命运正悬于一小群献身科学的人肩头。_ _原型机已经完成，现在你急需在实践中进行实验。_ 你被给定一棵完全被海狸占据的树。树是一种无环的连通无向图。该树包含 #cf_span[n] 个顶点，第 #cf_span[i] 个顶点上有 #cf_span[ki] 只海狸。 “Beavermuncher-0xFF” 的工作原理如下：当它位于某个顶点 #cf_span[u] 时，它可以移动到与其相连的顶点 #cf_span[v]，并吃掉位于顶点 #cf_span[v] 的 *恰好一只* 海狸。如果顶点 #cf_span[v] 中没有海狸，则无法移动到该顶点。“Beavermuncher-0xFF” *不能* 停留在某个顶点并吃掉该顶点的海狸。“Beavermuncher-0xFF” 必须持续移动，不能停歇。为什么“Beavermuncher-0xFF”要这样工作？因为开发者没有为其预留电池位置，吃掉海狸是将其质量转化为纯能量的必要手段。保证海狸会被发生的事件震惊，因此它们无法从树的某个顶点移动到另一个顶点。至于“Beavermuncher-0xFF”，只要满足上述条件，它就可以沿每条边双向移动。树的根位于顶点 #cf_span[s]。这意味着“Beavermuncher-0xFF”从顶点 #cf_span[s] 开始其任务，并且在实验结束时必须返回该顶点，因为没人会去高处把它取下来。请确定“Beavermuncher-0xFF”最多能吃掉多少只海狸并返回起始顶点。第一行包含整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 105]）。第二行包含 #cf_span[n] 个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 105]）—— 对应顶点上的海狸数量。接下来的 #cf_span[n - 1] 行描述树的结构，每行包含两个用空格分隔的整数，表示一条边连接的两个顶点。顶点编号从 #cf_span[1] 到 #cf_span[n]。最后一行包含整数 #cf_span[s] —— 起始顶点的编号（#cf_span[1 ≤ s ≤ n]）。请输出“Beavermuncher-0xFF”吃掉的海狸的最大数量。请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_（也可使用 _%I64d_）。 ## Input 第一行包含整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 105]）。第二行包含 #cf_span[n] 个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 105]）—— 对应顶点上的海狸数量。接下来的 #cf_span[n - 1] 行描述树的结构，每行包含两个用空格分隔的整数，表示一条边连接的两个顶点。顶点编号从 #cf_span[1] 到 #cf_span[n]。最后一行包含整数 #cf_span[s] —— 起始顶点的编号（#cf_span[1 ≤ s ≤ n]）。 ## Output 请输出“Beavermuncher-0xFF”吃掉的海狸的最大数量。请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_（也可使用 _%I64d_）。 [samples]

**Definitions** Let $ T = (V, E) $ be a tree with $ n = |V| $ vertices. Let $ k_i \in \mathbb{Z}^+ $ denote the number of beavers at vertex $ i \in V $. Let $ s \in V $ be the root vertex (starting and ending position of the Beavermuncher). Let $ G = (V, E) $ be the undirected tree with adjacency structure. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq k_i \leq 10^5 $ for all $ i \in V $ 3. The Beavermuncher starts at vertex $ s $ and must return to $ s $. 4. The Beavermuncher moves along edges; each move consumes exactly one beaver from the *destination* vertex. 5. The Beavermuncher cannot remain stationary; it must move at every step. 6. Movement to a vertex $ v $ is only allowed if $ k_v > 0 $. 7. The Beavermuncher may traverse any edge multiple times, provided the beaver constraint is satisfied. **Objective** Maximize the total number of beavers eaten, i.e., the total number of moves made, under the constraint that the Beavermuncher begins and ends at vertex $ s $. Formally, find the maximum number of moves $ M $ such that there exists a closed walk $ W $ starting and ending at $ s $, where each edge traversal corresponds to consuming one beaver from the destination vertex of that traversal, and no vertex is visited as a destination when it has zero beavers left.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Beavermuncher-0xFF",
    "description": {
      "content": "_\"Eat a beaver, save a tree!\" — That will be the motto of ecologists' urgent meeting in Beaverley Hills._ _And the whole point is that the population of beavers on the Earth has reached incredible si",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF77C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_\"Eat a beaver, save a tree!\" — That will be the motto of ecologists' urgent meeting in Beaverley Hills._\n\n_And the whole point is that the population of beavers on the Earth has reached incredible si...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_\"吃掉海狸，拯救树木！\"——这是比弗利山生态学家紧急会议的口号。_\n\n_而问题的症结在于，地球上海狸的数量已经达到了惊人的规模！每天它们的数量都会增加数倍，却丝毫没有意识到自己对树木的病态痴迷如何危害自然与人类。大气中的氧气含量已降至17%，而世界顶尖学者认为，这还远非终点。_\n\n_在上世纪50年代中期，一群苏联科学家成功预见了海狸的危机，并研发出一项秘密技术来清理领土。这项技术拥有一个神秘的名...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n = |V| $ vertices.  \nLet $ k_i \\in \\mathbb{Z}^+ $ denote the number of beavers at vertex $ i \\in V $.  \nLet $ s \\in V $ be the root vertex (start...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments