{"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 write a positive integer on each vertex in $T$ and calculate our _score_ as follows:\n\n*   On each edge, write the smaller of the integers written on the two endpoints.\n*   Let our score be the sum of the integers written on all the edges.\n\nFind 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.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10000$\n*   $1 \\leq a_i,b_i \\leq N$\n*   $1 \\leq c_i \\leq 10^5$\n*   The given graph is a tree.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$:$\n$a_{N-1}$ $b_{N-1}$\n$c_1$ $\\ldots$ $c_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"m_solutions2019_d","tags":[],"sample_group":[["5\n1 2\n2 3\n3 4\n4 5\n1 2 3 4 5","10\n1 2 3 4 5\n\nIf 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."],["5\n1 2\n1 3\n1 4\n1 5\n3141 59 26 53 59","197\n59 26 3141 59 53\n\n$c_1,c_2,\\ldots,c_N$ may not be pairwise distinct."]],"created_at":"2026-03-03 11:01:14"}}