<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 time_to_mark_child(self, child_num):
        return 2 if child_num % 2 == 0 else 1

    # time taken to mark subtree rooted at node with parent
    def time_taken_to_mark_subtree(self, adjacent_nodes, unvisited_adjacent_nodes, two_most_time_consuming_children, node, parent, time_taken_to_mark_subtree):
        if (parent, node) in time_taken_to_mark_subtree:
            return time_taken_to_mark_subtree[(parent, node)]
       
        for child in unvisited_adjacent_nodes[node]:
            if child == parent:
                continue
            time_to_mark_child_subtree = self.time_taken_to_mark_subtree(adjacent_nodes, unvisited_adjacent_nodes, two_most_time_consuming_children,
                                                                         child, node, time_taken_to_mark_subtree)
            time_taken_to_child_branch = self.time_to_mark_child(child) + time_to_mark_child_subtree
            if node not in two_most_time_consuming_children:
                two_most_time_consuming_children[node] = [(child, time_taken_to_child_branch)]
            elif len(two_most_time_consuming_children[node]) == 1:
                if time_taken_to_child_branch >= two_most_time_consuming_children[node][0][1]:
                    two_most_time_consuming_children[node].insert(0, (child, time_taken_to_child_branch))
                else:
                    two_most_time_consuming_children[node].append((child, time_taken_to_child_branch))
            elif time_taken_to_child_branch >= two_most_time_consuming_children[node][0][1]:
                two_most_time_consuming_children[node].insert(0, (child, time_taken_to_child_branch))
                two_most_time_consuming_children[node].pop()
            elif time_taken_to_child_branch > two_most_time_consuming_children[node][1][1]:
                two_most_time_consuming_children[node][1] = (child, time_taken_to_child_branch)
        unvisited_adjacent_nodes[node] = [parent] if parent in unvisited_adjacent_nodes[node] else []

        time = 0
        if node in two_most_time_consuming_children:
            if two_most_time_consuming_children[node][0][0] != parent:
                time = two_most_time_consuming_children[node][0][1]
            else:
                time = two_most_time_consuming_children[node][1][1]
        time_taken_to_mark_subtree[(parent, node)] = time
        return time

    def timeTaken(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        adjacent_nodes = {}
        unvisited_adjacent_nodes = {}
        for u,v in edges:
            if u not in adjacent_nodes:
                adjacent_nodes[u] = []
                unvisited_adjacent_nodes[u] = []
            if v not in adjacent_nodes:
                adjacent_nodes[v] = []
                unvisited_adjacent_nodes[v] = []
            adjacent_nodes[u].append(v)
            adjacent_nodes[v].append(u)
            unvisited_adjacent_nodes[u].append(v)
            unvisited_adjacent_nodes[v].append(u)
        
        two_most_time_consuming_children = {}
        
        time_taken_to_mark_subtree = {}
        for u,v in edges:
            # self.time_taken_to_mark_subtree(adjacent_nodes, u, v, time_taken_to_mark_subtree)
            # self.time_taken_to_mark_subtree(adjacent_nodes, v, u, time_taken_to_mark_subtree)
            if len(adjacent_nodes[v]) == 1:
                self.time_taken_to_mark_subtree(adjacent_nodes, unvisited_adjacent_nodes, two_most_time_consuming_children, u, v, time_taken_to_mark_subtree)
            if len(adjacent_nodes[u]) == 1:
                self.time_taken_to_mark_subtree(adjacent_nodes, unvisited_adjacent_nodes, two_most_time_consuming_children, v, u, time_taken_to_mark_subtree)

        time_taken = [0 for i in range(n+1)]
        # for u in adjacent_nodes:
        #     time = 0
        #     for child in adjacent_nodes[u]:
        #         time_to_mark_child_subtree = time_taken_to_mark_subtree[(u, child)]
        #         time = max(time, time_to_mark_child_subtree + self.time_to_mark_child(child))
        #     time_taken[u] = time
        for u,v in edges:
            time_taken[u] = max(time_taken[u], self.time_to_mark_child(v) + time_taken_to_mark_subtree[(u, v)])
            time_taken[v] = max(time_taken[v], self.time_to_mark_child(u) + time_taken_to_mark_subtree[(v, u)])
        return time_taken
140253