Страна R состоит из n городов и n - 1 двусторонних дорог, расположенных так, что из любого города можно добраться до любого другого. Президент этой страны решил выбрать столицу. Как только столица будет выбрана, все жители страны съедутся на парад в столицу. Известно, что в i-м городе проживает v_i жителей. Решение, какой же именно город станет столицей, еще не принято, так как еще не до конца понятно, что же для страны будет выгоднее: с одной стороны, можно неплохо простимулировать транспортную систему страны, если сделать столицу в достаточно удаленном и малонаселенном городе, а с другой стороны, столица, расположенная в крупном городе поближе к центру, будет быстро развиваться и тоже потянет экономику вверх. Поэтому президент хочет посчитать для каждого города i, сколько суммарно дорог преодолеют все жители страны, чтоб добраться до столицы, если сделать ее в городе i. Без сомнения, обладая этой информацией, он примет правильное решение и приведет страну к успеху и процветанию.