E. Beavermuncher-0xFF

Codeforces

IDCF80E

Time3000ms

Memory256MB

Difficulty—

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 ≤ 10^5]）。第二行包含 #cf_span[n] 个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 10^5]）—— 各顶点上的海狸数量。接下来 #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 ≤ 10^5]）。第二行包含 #cf_span[n] 个整数 #cf_span[ki]（#cf_span[1 ≤ ki ≤ 10^5]）—— 各顶点上的海狸数量。接下来 #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 $ n \in \mathbb{Z}^+ $ be the number of vertices in a tree. Let $ k_i \in \mathbb{Z}^+ $ denote the number of beavers at vertex $ i $, for $ i \in \{1, \dots, n\} $. Let $ T = (V, E) $ be a tree with vertex set $ V = \{1, \dots, n\} $ and edge set $ E $. Let $ s \in V $ be the root vertex (starting and ending position of the Beavermuncher). **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq k_i \leq 10^5 $ for all $ i \in V $ 3. The graph is a tree (connected, acyclic, $ |E| = n-1 $) 4. The Beavermuncher starts and ends at vertex $ s $. 5. Movement: From current vertex $ u $, the Beavermuncher may traverse an edge to neighbor $ v $ **only if** $ k_v > 0 $, and upon entering $ v $, it eats **exactly one** beaver from $ k_v $. 6. The Beavermuncher cannot remain stationary; it must move at every step. 7. Beavers do not move. **Objective** Maximize the total number of beavers eaten, subject to the constraint that the Beavermuncher returns to $ s $ after a finite sequence of moves. Formally, find the maximum number of beavers eaten over all valid walks $ W $ starting and ending at $ s $, such that: - Each traversal of edge $ (u,v) $ requires $ k_v > 0 $, and reduces $ k_v $ by 1. - The walk is finite and returns to $ s $. - No vertex is visited more than $ k_i $ times (since beavers are consumed). Let $ m $ be the maximum number of beavers eaten under these rules. Compute $ m $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. 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": "CF80E"
  },
  "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年代中期，一组苏联科学家成功预见了海狸的危机，并研发出一项秘密技术以清理领土。这项技术名为神秘的“Beav...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a tree.  \nLet $ k_i \\in \\mathbb{Z}^+ $ denote the number of beavers at vertex $ i $, for $ i \\in \\{1, \\dots, n\\} $.  \nLet $ T ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments