<p>There exists an <strong>undirected</strong> tree with <code>n</code> nodes numbered <code>0</code> to <code>n - 1</code>. You are given a 2D integer array <code>edges</code> of length <code>n - 1</code>, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that there is an edge between nodes <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> in the tree.</p>

<p>Initially, <strong>all</strong> nodes are <strong>unmarked</strong>. For each node <code>i</code>:</p>

<ul>
	<li>If <code>i</code> is odd, the node will get marked at time <code>x</code> if there is <strong>at least</strong> one node <em>adjacent</em> to it which was marked at time <code>x - 1</code>.</li>
	<li>If <code>i</code> is even, the node will get marked at time <code>x</code> if there is <strong>at least</strong> one node <em>adjacent</em> to it which was marked at time <code>x - 2</code>.</li>
</ul>

<p>Return an array <code>times</code> where <code>times[i]</code> is the time when all nodes get marked in the tree, if you mark node <code>i</code> at time <code>t = 0</code>.</p>

<p><strong>Note</strong> that the answer for each <code>times[i]</code> is <strong>independent</strong>, i.e. when you mark node <code>i</code> all other nodes are <em>unmarked</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">edges = [[0,1],[0,2]]</span></p>

<p><strong>Output:</strong> [2,4,3]</p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/06/01/screenshot-2024-06-02-122236.png" style="width: 500px; height: 241px;" /></p>

<ul>
	<li>For <code>i = 0</code>:

	<ul>
		<li>Node 1 is marked at <code>t = 1</code>, and Node 2 at <code>t = 2</code>.</li>
	</ul>
	</li>
	<li>For <code>i = 1</code>:
	<ul>
		<li>Node 0 is marked at <code>t = 2</code>, and Node 2 at <code>t = 4</code>.</li>
	</ul>
	</li>
	<li>For <code>i = 2</code>:
	<ul>
		<li>Node 0 is marked at <code>t = 2</code>, and Node 1 at <code>t = 3</code>.</li>
	</ul>
	</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">edges = [[0,1]]</span></p>

<p><strong>Output:</strong> [1,2]</p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/06/01/screenshot-2024-06-02-122249.png" style="width: 500px; height: 257px;" /></p>

<ul>
	<li>For <code>i = 0</code>:

	<ul>
		<li>Node 1 is marked at <code>t = 1</code>.</li>
	</ul>
	</li>
	<li>For <code>i = 1</code>:
	<ul>
		<li>Node 0 is marked at <code>t = 2</code>.</li>
	</ul>
	</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">edges = </span>[[2,4],[0,1],[2,3],[0,2]]</p>

<p><strong>Output:</strong> [4,6,3,5,5]</p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/06/03/screenshot-2024-06-03-210550.png" style="height: 266px; width: 500px;" /></p>
</div>

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

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= edges[i][0], edges[i][1] &lt;= n - 1</code></li>
	<li>The input is generated such that <code>edges</code> represents a valid tree.</li>
</ul>

"""
2 way dp

dp1[i] = max delay for this subtree rooted at i
dp2[i] = max delay for subtree of everything above i

dp1[i] = max dp1[child] + d_child for all child
dp2[i] = delay from i to par[i], max of dp2[par[i]] and dp1[par[i]] for a childs != i
"""

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        def delay(x):
            if x % 2 == 0:
                return 2
            return 1

        n = len(edges) + 1
        root = 0
        g = [[] for i in range(n)]
        p = [-1] * n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        
        dp1 = [0] * n
        dp2 = [0] * n
        def dfs1(cur, par):
            p[cur] = par
            mx = 0
            for v in g[cur]:
                if v == par:
                    continue
                dfs1(v, cur)
                mx = max(mx, dp1[v] + delay(v))
            # get dp
            dp1[cur] = mx

        def dfs2(cur, par):
            # dp2[i] = delay from i to par[i], max of dp2[par[i]] and dp1[par[i]] for a childs != i
            # calc dp2 here
            if par == -1:
                pd = 0
            else:
                pd = dp2[cur]

            # calc the upwards subtrees for cur
            childs = [x for x in g[cur] if x != par]
            nc = len(childs)
            if nc > 0:
                arr = [0] * nc
                for i in range(nc):
                    child = childs[i]
                    arr[i] = delay(child) + dp1[child]
                # pref and suff max
                pref = [0] * nc
                suff = [0] * nc
                pref[0] = arr[0]
                for i in range(1, nc):
                    pref[i] = max(pref[i-1], arr[i])
                suff[nc-1] = arr[nc-1]
                for i in range(nc-2, -1, -1):
                    suff[i] = max(suff[i+1], arr[i])
                
                # print('dfs2 cur', cur)
                # print('pref', pref)
                # print('suff', suff)
                # push down to children
                for i in range(nc):
                    others = 0
                    if i > 0:
                        others = max(others, pref[i-1])
                    if i < nc-1:
                        others = max(others, suff[i+1])
                    here = max(others, pd)
                    # print("here", here, pd)
                    dp2[childs[i]] = here + delay(cur)
                    
            for v in g[cur]:
                if v == par:
                    continue
                dfs2(v, cur)
        
        dfs1(0, -1)
        dfs2(0, -1)

        print('dp1', dp1)
        print('dp2', dp2)

        ans = [max(dp1[i], 0 if p[i] == -1 else dp2[i]) for i in range(n)]
        print(ans)
        return ans

130934