Добрый день!

Как решать такую задачу Сумма ? Я думал как-то при помощи DSU, но не придумал как пересчитывать сумму при объединении множеств.

P.S. 472D - Уроки дизайна задач: обратные задачи в этой задаче сказано, что посчитать расстояния между всеми парами вершин в дереве это очень просто. Можете рассказать как? Дейкстра(и другие аналоги) же от каждой вершины по времени не зайдет