{"problem":{"name":"[ICPC 2024 Xi'an I] Fix the Tree","description":{"content":"You are given a tree consisting of $n$ vertices. Each vertex $i$ of this tree has a value $w_i$ assigned to it. Now the vertex $u$ will be broken. Once it's broken, vertex $u$ and all edges with one ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10555"},"statements":[{"statement_type":"Markdown","content":"You are given a tree consisting of $n$ vertices. Each vertex $i$ of this tree has a value $w_i$ assigned to it.\n\nNow the vertex $u$ will be broken. Once it's broken, vertex $u$ and all edges with one end at vertex $u$ will be removed from the tree.\n\nTo make the tree connected, you can do the following operation any number of times(possibly zero) in any order:\n\n- First choose two vertices $u$ and $v$ from the tree;\n- Then pay $w_u+w_v$ coins, and add an edge between vertices $u$ and $v$;\n- At last, replace $w_u+1$ with $w_u$, replace $w_v+1$ with $w_v$.\n\nYour task is to calculate the minimum number of coins to be paid.\n\nBut you don't know which vertex $u$ is, so you need to find the answer for each $1\\le u\\le n$. Please answer all the queries independently.\n\n## Input\n\nThe first line contains a single integer $n(2\\le n\\le 10^6)$ --- the number of vertices in this tree.\n\nThe next line contains $n$ numbers, the $i$ -th number is $w_i(1\\le w_i\\le n)$.\n\nThe next $n-1$ lines contain a description of the tree's edges. The $i$ -th of these lines contains two integers $u_i$ and $v_i(1\\le u_i,v_i\\le n) $ --- the numbers of vertices connected by the $i$ -th edge.\n\nIt is guaranteed that the given edges form a tree.\n\n## Output\n\nPrint $n$ integers, the $i$ -th integer is the answer when $u=i$.\n\n[samples]\n\n## Note\n\n给定一个有 $n$ 个点组成的树，每个点有一个权值 $w_i$。  \n点 $u$ 和相邻的边被删除。  \n你可以进行以下操作任意次数（可以为 $0$）,让树重新成为连通图：\n1. 选择两个点 $u$、$v$；\n2. 花费 $w_u + w_v$ 的代价连接一条边 $(u,v)$；\n3. $w_u \\leftarrow w_u+1,w_v \\leftarrow w_v+1$。\n\n对于每个 $u$ 计算最小代价。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10555","tags":["2024","O2优化","ICPC","西安"],"sample_group":[["6\n1 1 1 1 1 1\n1 2\n1 3\n1 4\n2 5\n2 6","4 4 0 0 0 0"],["4\n1 2 3 4\n1 2\n1 3\n1 4","12 0 0 0"],["7\n1 2 3 4 5 6 7\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7","5 12 16 0 0 0 0"]],"created_at":"2026-03-03 11:09:25"}}