Tổng khoảng cách trong cây trong C++

Cho cây N đỉnh (0..N-1) và N-1 cạnh. Tìm mảng ans với ans[i] = tổng khoảng cách từ đỉnh i đến tất cả đỉnh khác.

Ví dụ: N=6, edges=[[0,1],[0,2],[2,3],[2,4],[2,5]] → [8,12,6,10,10,10].

Giải thuật

1. DFS 1 (dfs1): tính cnt[u] = số nút trong cây con u, ans[u] = tổng khoảng cách từ u đến các nút trong cây con.
2. DFS 2 (dfs2): rerooting. Khi chuyển gốc từ parent sang child: ans[child] = ans[parent] - cnt[child] + (N - cnt[child]).
3. Trả về mảng ans.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++) cout << v[i] << ", ";
    cout << "]"<<endl;
}
class Solution {
public:
    void dfs1(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                dfs1(child, node);
                cnt[node] += cnt[child];
                ans[node] += cnt[child] + ans[child];
            }
        }
    }
    void dfs2(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - cnt[child] + N - cnt[child];
                dfs2(child, node);
            }
        }
    }
    vector<int> ans, cnt;
    vector<int> graph[10005];
    int N;
    vector<int> sumOfDistancesInTree(int N, vector<vector<int> >& edges) {
        this->N = N;
        ans = vector<int>(N);
        cnt = vector<int>(N, 1);
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        dfs1(0, -1);
        dfs2(0, -1);
        return ans;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}};
    print_vector(ob.sumOfDistancesInTree(6, v));
}

Đầu vào

{{0,1},{0,2},{2,3},{2,4},{2,5}}

Đầu ra

[8, 12, 6, 10, 10, 10, ]