Сумма расстояний до всех вершин дерева

Дано дерево из n вершин (0..n-1), n-1 рёбер edges. Для КАЖДОЙ вершины v верните сумму расстояний (в рёбрах) от v до всех остальных вершин дерева. Результат - массив длины n. Наивно считать BFS от каждой вершины отдельно - O(n^2). Эффективный приём (rerooting): посчитайте ответ для одной вершины обычным обходом, а для остальных пересчитайте его через родителя за O(1) при переходе по ребру.