sum of distances in tree

1    vector<unordered_set<int>> tree;
2    vector<int> res, count;
3
4    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
5        tree.resize(N);
6        res.assign(N, 0);
7        count.assign(N, 1);
8        for (auto e : edges) {
9            tree[e[0]].insert(e[1]);
10            tree[e[1]].insert(e[0]);
11        }
12        dfs(0, -1);
13        dfs2(0, -1);
14        return res;
15
16    }
17
18    void dfs(int root, int pre) {
19        for (auto i : tree[root]) {
20            if (i == pre) continue;
21            dfs(i, root);
22            count[root] += count[i];
23            res[root] += res[i] + count[i];
24        }
25    }
26
27    void dfs2(int root, int pre) {
28        for (auto i : tree[root]) {
29            if (i == pre) continue;
30            res[i] = res[root] - count[i] + count.size() - count[i];
31            dfs2(i, root);
32        }
33    }
34

1    int[] res, count;
2    ArrayList<HashSet<Integer>> tree;
3    public int[] sumOfDistancesInTree(int N, int[][] edges) {
4        tree = new ArrayList<HashSet<Integer>>();
5        res = new int[N];
6        count = new int[N];
7        for (int i = 0; i < N ; ++i)
8            tree.add(new HashSet<Integer>());
9        for (int[] e : edges) {
10            tree.get(e[0]).add(e[1]);
11            tree.get(e[1]).add(e[0]);
12        }
13        dfs(0, -1);
14        dfs2(0, -1);
15        return res;
16    }
17
18    public void dfs(int root, int pre) {
19        for (int i : tree.get(root)) {
20            if (i == pre) continue;
21            dfs(i, root);
22            count[root] += count[i];
23            res[root] += res[i] + count[i];
24        }
25        count[root]++;
26    }
27
28
29    public void dfs2(int root, int pre) {
30        for (int i : tree.get(root)) {
31            if (i == pre) continue;
32            res[i] = res[root] - count[i] + count.length - count[i];
33            dfs2(i, root);
34        }
35    }
36