Intuition of O(n) solution based on “undirected” tree

My solution is in principle the same with the O(n) solutions posted by other people. But their explain is more or less based on directed tree while my intuition based directly on undirected tree, as mentioned in the original problem. In an undirected, every node simply “connects” to each other, and their roles are equivalent. It is wired to call any of them parent/children/root nodes. Although you can select an arbitrary node as root and create a directed tree, you don’t need to. Explanation:

• Disconnecting any edge, say [i, j], would break the tree into two subtrees, one with node i and another with node j
• Use count[i,j] to represent the number of nodes in subtree with node i if disconnect edge [i, j]. Then count[j,i] = N – count[i,j]
• For any adjacent node pair i and j: sum[j] = sum[i] – count[j,i] + count[i,j]
• Calculate sum of distance for one arbitrary node, and use the fomula to calculate the others.

Steps

• Create node representation of tree from given edge list, O(n) time & space
• Calculate count[i,j], dp, O(n) time & space
• Calculate sum[0], bfs, O(n) time & space
• Derive sums for all other nodes, bfs, O(n) time & space

O(n) time & space in total.