Maximum Sum of Minimum

AtCoder

IDm_solutions2019_d

Time2000ms

Memory256MB

Difficulty—

You are given a tree with $N$ vertices $1,2,\ldots,N$, and positive integers $c_1,c_2,\ldots,c_N$. The $i$\-th edge in the tree $(1 \leq i \leq N-1)$ connects Vertex $a_i$ and Vertex $b_i$. We will write a positive integer on each vertex in $T$ and calculate our _score_ as follows: * On each edge, write the smaller of the integers written on the two endpoints. * Let our score be the sum of the integers written on all the edges. Find the maximum possible score when we write each of $c_1,c_2,\ldots,c_N$ on one vertex in $T$, and show one way to achieve it. If an integer occurs multiple times in $c_1,c_2,\ldots,c_N$, we must use it that number of times. ## Constraints * $1 \leq N \leq 10000$ * $1 \leq a_i,b_i \leq N$ * $1 \leq c_i \leq 10^5$ * The given graph is a tree. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $\ldots$ $c_N$ [samples]

Samples

Input #1

Output #1

10
1 2 3 4 5

If we write $1,2,3,4,5$ on Vertex $1,2,3,4,5$, respectively, the integers written on the four edges will be $1,2,3,4$, for the score of $10$. This is the maximum possible score.

Input #2

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

Output #2

197
59 26 3141 59 53

$c_1,c_2,\ldots,c_N$ may not be pairwise distinct.

API Response (JSON)

{
  "problem": {
    "name": "Maximum Sum of Minimum",
    "description": {
      "content": "You are given a tree with $N$ vertices $1,2,\\ldots,N$, and positive integers $c_1,c_2,\\ldots,c_N$. The $i$\\-th edge in the tree $(1 \\leq i \\leq N-1)$ connects Vertex $a_i$ and Vertex $b_i$. We will wr",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "m_solutions2019_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree with $N$ vertices $1,2,\\ldots,N$, and positive integers $c_1,c_2,\\ldots,c_N$. The $i$\\-th edge in the tree $(1 \\leq i \\leq N-1)$ connects Vertex $a_i$ and Vertex $b_i$.\nWe will wr...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments