Разбор добавил Иван Смирнов

Решим задачу с помощью модифицированной системы непересекающихся множеств (DSU), позволяющей, помимо нахождения множества для каждого элемента, найти вес этого множества. Для этого введем массив sum[MAXN]. sum[i] имеет смысл, только если i - представитель какого-либо множества. Тогда в этом поле хранится вес соответствующего множества. Кроме этого, модифицируем операции объединения множеств и поиска представителя. Пусть при объединении двух множеств мы нашли их представителей - X и Y - и собираемся сделать Y представителем для X. Тогда, помимо этого, мы должны прибавить к весу Y вес X. sum[X] потеряло смысл, т. к. X перестало быть представителем, но для корректной работы его необходимо обнулить (некоторые элементы поддерева X еще могут иметь X в качестве непосредственного представителя). При поиске представителя обновление производится аналогично. Когда мы, согласно эвристике, обновляем представителя для всех вершин, встретившихся "по пути", мы должны обновить и значение их суммы, перенеся ее из обновляемой вершины в ее нового представителя указанным выше способом. Очевидно, как теперь отвечать на запросы. При добавлении ребра (u, v, w) объединим вершины u и v в одно множество (если это нужно) и добавим к весу его представителя число w. Для нахождения веса компоненты связности ребра v выведем вес его представителя.