<p>There is an undirected connected tree with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> edges.</p>

<p>You are given the integer <code>n</code> and the array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> in the tree.</p>

<p>Return an array <code>answer</code> of length <code>n</code> where <code>answer[i]</code> is the sum of the distances between the <code>i<sup>th</sup></code> node in the tree and all other nodes.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist1.jpg" style="width: 304px; height: 224px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
<strong>Output:</strong> [8,12,6,10,10,10]
<strong>Explanation:</strong> The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist2.jpg" style="width: 64px; height: 65px;" />
<pre>
<strong>Input:</strong> n = 1, edges = []
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist3.jpg" style="width: 144px; height: 145px;" />
<pre>
<strong>Input:</strong> n = 2, edges = [[1,0]]
<strong>Output:</strong> [1,1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>The given input represents a valid tree.</li>
</ul>

class Solution(object):
    def sumOfDistancesInTree(self, N, edges):
        #build adj list

        #dfs post "prop" - 1. dfs 2. += node count  child vals
        counts = [1] * N
        res = [0] * N
        adj = defaultdict(list)

        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        def propagateUpRootAns(num, parent):
            for i in adj[num]:
                if i != parent:
                    # post-order, child results come first
                    propagateUpRootAns(i, num)
                    counts[num] += counts[i]
                    res[num] += counts[i] + res[i]
                
        def recurDownChildAns(num, parent):
        #
            for i in adj[num]:
                if i != parent:
                    res[i] = res[num] + N - 2*counts[i]
                    recurDownChildAns(i, num)
                    
        propagateUpRootAns(0, None)
        recurDownChildAns(0, None)
        return res
        """
            d(0, 3) = d(0,1) + d(1,2)
            O->X->Y->Z d(0,z) = d(O,x) + d(x,z) or d(0,y) + d(y,z)

            build dp of "segment" lengths:

            (2,3) = 1
            2,4 = 1
            leaf legnths seed from edges, then:
            - traverse parents in reverse i.e. find 2 from 3,4,5, find 0 from 2

            how to optimize this compuation? d(0,3), d0,4, d0,5. d 

            based on 0, can traverse to 1 and 2, find 0,1 in dp, find 
            
            1 + child_count * child_vals
            0,2:1 +  [1,1,1 + 1] * 3
            2,3:1, 2,4:1 (2,5:1 + 1 * 1)

            d2 = 1 + 1  * d5(1 + 1 )
            
            total_x = sum(x) + sum(y)

           0x                   2               1
        1y    2           0   3 4 5       6   7   0
       6 7    3 4 5         1                       2
                            6 7                     3 4 5
     2 sub + 3 cnt   3 sub + 4 cnt
     9 + 3
     ans[1] = ans[0]:12 + N:8 - 2county:6 = 12 + 8 - 6 = 14
    ans[x] - count(y):4 + count(x'):4
    ans[y] = ans[x] + N:8 - 2county:8

            ans(y) = sub(y) + sub(x) + count(x)
            ans(x) = sub(x) + sub(y) + count(y)
            ans(x) - ans(y) = count(y) - count(x)
            ans(x) = ans(y) + count(y) - count(x)
            ans(y) = ans(x) - count(y) + count(x)
                    = ans(x) - (N - countx) + count(x) = ansx - N + 2countx = 8 - 6 + 2
                    = ans(x) - count(y) + (N - county) = ansx + N - 2county = 
                    
            
            county = N - countx
            countx = N - county
            8 = 6 + 4 - 2
            ans y
            we don't have accurate countx?

            ans(1) = ans(0）：8 - N:6 + 2 count(x):12 = 14
               0 1 2 3 4 5
        cnt   [6 1 4 1 1 1 ]
        ans   [8   3      ]
                O
            1       2
        3   4      7  8
            5 6         9
                        10
        [1]
        []
        1. propogate up (post order) sub sums and sub counts to get ans(x)
        2. propogate down from x using ans(x)  and formula
        
        """
43670