1
var sumOfDistancesInTree = function (n, edges) {
2
  let graph = {};
3
  for (let [start, end] of edges) {
4
    if (!graph[start]) graph[start] = [];
5
    if (!graph[end]) graph[end] = [];
6
    graph[start].push(end);
7
    graph[end].push(start);
8
  }
9

10
  let visited = new Set(),
11
    distanceFromZero = 0,
12
    totalChildren = {};
13
  // Find the sum distance from node O to all other nodes and the total children of each node
14
  function dfs(node, sum = 0) {
15
    visited.add(node);
16
    distanceFromZero += sum;
17
    if (!graph[node]) return;
18
    let child = 0;
19
    for (let nextNode of graph[node]) {
20
      if (visited.has(nextNode)) continue;
21
      child += dfs(nextNode, sum + 1);
22
    }
23
    totalChildren[node] = child;
24
    return child + 1;
25
  }
26
  dfs(0);
27

28
  let dp = [distanceFromZero];
29
  visited = new Set();
30
  function findDistance(node) {
31
    visited.add(node);
32
    if (!graph[node]) return;
33
    for (let nextNode of graph[node]) {
34
      if (visited.has(nextNode)) {
35
        dp[node] = dp[nextNode] + (n - 2);
36
        break;
37
      }
38
    }
39
    if (node !== 0 && totalChildren[node]) dp[node] -= totalChildren[node] * 2;
40
    for (let nextNode of graph[node]) {
41
      if (visited.has(nextNode)) continue;
42
      else findDistance(nextNode);
43
    }
44
  }
45

46
  findDistance(0);
47
  return dp;
48
};