{"problem":{"name":"L. Выбор столицы","description":{"content":"Страна R состоит из n городов и n - 1 двусторонних дорог, расположенных так, что из любого города можно добраться до любого другого. Президент этой страны решил выбрать столицу. Как только столица буд","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10120L"},"statements":[{"statement_type":"Markdown","content":"Страна R состоит из n городов и n - 1 двусторонних дорог, расположенных так, что из любого города можно добраться до любого другого. Президент этой страны решил выбрать столицу. Как только столица будет выбрана, все жители страны съедутся на парад в столицу. Известно, что в i-м городе проживает vi жителей. Решение, какой же именно город станет столицей, еще не принято, так как еще не до конца понятно, что же для страны будет выгоднее: с одной стороны, можно неплохо простимулировать транспортную систему страны, если сделать столицу в достаточно удаленном и малонаселенном городе, а с другой стороны, столица, расположенная в крупном городе поближе к центру, будет быстро развиваться и тоже потянет экономику вверх. Поэтому президент хочет посчитать для каждого города i, сколько суммарно дорог преодолеют все жители страны, чтоб добраться до столицы, если сделать ее в городе i. Без сомнения, обладая этой информацией, он примет правильное решение и приведет страну к успеху и процветанию.\n\nВ первой строке записано целое число n (1 ≤ n ≤ 100000) — количество городов в стране.\n\nВ следующей строке записаны n чисел vi (1 ≤ vi ≤ 108) — количества жителей в каждом городе.\n\nВ каждой из следующих n - 1 строк записаны два числа ai и bi (1 ≤ ai, bi ≤ n) — номера городов соединенных дорогой.\n\nВыведите n чисел. i-е число должно равняться суммарно пройденному расстоянию всех жителей страны до города i.\n\n## Входные Данные\n\nВ первой строке записано целое число n (1 ≤ n ≤ 100000) — количество городов в стране.В следующей строке записаны n чисел vi (1 ≤ vi ≤ 108) — количества жителей в каждом городе.В каждой из следующих n - 1 строк записаны два числа ai и bi (1 ≤ ai, bi ≤ n) — номера городов соединенных дорогой.\n\n## Выходные Данные\n\nВыведите n чисел. i-е число должно равняться суммарно пройденному расстоянию всех жителей страны до города i.\n\n## Пример\n\nВходные данные57 3 2 5 41 21 33 43 5Выходные данные23 38 22 33 35\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of cities.  \nLet $ v_i \\in \\mathbb{Z}^+ $ be the population of city $ i $, for $ i \\in \\{1, \\dots, n\\} $.  \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $, representing the road network.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100000 $  \n2. $ 1 \\leq v_i \\leq 10^8 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Each edge $ (a_i, b_i) \\in E $ connects two distinct cities.\n\n**Objective**  \nFor each city $ i \\in \\{1, \\dots, n\\} $, compute:  \n$$\nS_i = \\sum_{j=1}^{n} v_j \\cdot d(j, i)\n$$  \nwhere $ d(j, i) $ is the shortest path distance (number of edges) between cities $ j $ and $ i $ in tree $ T $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10120L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}