<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>

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        # yikes, have to figure out the mark time from each node i, but can only take O(n) time total
        # from root:
            # odd children will get marked at t=1
                # odd children get marked t=2, even at t=3
            # even children get marked t=2
                # odd at t=3, even at t=4, ...
        # now start from an odd child of root:
            # root gets marked at t=1 or 2 based on even/oddness
            # root's other children get marked at t={1,2}+odd/even-ness
            # my children:
                # marked at t={1,2} based on even/odd
                    # vs t=1+{1,2}
                        # or t=2+{1,2} if I'm odd
                        # ie, LHS of tree decreases by val(c)
                        # RHS of tree increases by val(root)
            # now take a child of myself:
                # its descendants decrease by val(c2)
                # my other child increases by val(c)
                # the root/parent increases by val(c) (+val(root))
                # so if we track the max() of each?
            # leaf node:
                # "child" (me) is 0, so just take max(parent's other edges) + odd/even of parent?
        graph = defaultdict(list)
        n = 0
        for [e1, e2] in edges:
            graph[e1].append(e2)
            graph[e2].append(e1)
            n = max(n, e1, e2)
        ans = [0]*(n+1)
        memo = {}
        parents = {}
        print(edges, n)
        def rec(i, parent):
            # iters.append((i, parent))
            parents[i] = parent
            my_val = 1 if i % 2 == 1 else 2
            tmax = 0
            for j in graph[i]:
                if j == parent:
                    continue
                tmax = max(tmax, rec(j, i))
            ret = tmax + my_val
            memo[i] = ret
            return ret
        rec(0, -1)
        print(memo)
        def get_vals(i, add):
            my_val = 1 if i % 2 == 1 else 2
            p = parents[i]
            cost = 0
            child_costs = []
            for j in graph[i]:
                if j == p:
                    # child_costs.append(add)
                    continue
                child_costs.append(memo[j])
            child_costs.sort()
            # my cost is the max of my children or my parent's passed down cost
            ans[i] = add
            if child_costs:
                ans[i] = max(child_costs[-1], ans[i])
            for j in graph[i]:
                if j == p:
                    continue
                # my child's cost is the max of: parent cost, my other children's costs
                new_add = add
                if child_costs and memo[j] != child_costs[-1]:
                    new_add = max(new_add, child_costs[-1])
                elif len(child_costs) > 1:
                    new_add = max(new_add, child_costs[-2])
                new_add += my_val
                # now calc my child's val, they'll need to add me into their parent cost
                get_vals(j, new_add)
            # print(i, add, cost)
            # ans[i] = cost
        get_vals(0, 0)
        return ans

110965