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

from collections import defaultdict
from typing import List

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        g = defaultdict(set)
        n = 0
        for u,v in edges:
            n = max(n,u)
            n = max(n,v)
            uv_weight = 1
            vu_weight = 1
            if v % 2 == 0:
                uv_weight = 2
            if u % 2 == 0:
                vu_weight = 2
            g[u].add((v,uv_weight))
            g[v].add((u,vu_weight))

        results = defaultdict(lambda: [])  # res[N]: stores top 2 max paths (length, nbr)
        v1 = {}  # v1[i]: node_i visited by node_{v1[i]}
        v2 = set()  # v2[(i,j)]: maxpath computed for curr, prev already

        count = [0]
        test = [0]
        def cache(curr, predecessor):
            # cache access for maxpath -- requires results[curr] to have already been constructed from all paths to curr's neighbours
            # Take the best path we have from curr that does not include predecessor
            best_result, source = results[curr][0]
            if source == predecessor:
                if len(results[curr]) == 1:
                    return 0
                best_result, _ = results[curr][1]  # Take second best since best is not a valid choice
            return best_result

        def get_weight(u,v):
            if v%2 == 0:
                return 2
            return 1

        def maxpath(curr: int, prev: int) -> int:
            count[0] += 1
            if curr in v1:
                original_visitor = v1[curr]
                if original_visitor != curr and (curr, original_visitor) not in v2:
                    stack = [curr]
                    visitor = original_visitor

                    # Backtrack to the original caller, collecting the path
                    while visitor != curr and (visitor, v1[visitor]) not in v2:
                        stack.append(visitor)
                        visitor = v1[visitor]
                    
                    # Add the visitor of the last node since wek now that node has a valid cached value which we will use to propagate backwards
                    stack.append(visitor)

                    # Now `stack` contains the sequence of nodes lacking the entry of itself to its predecessor appended with the very last node in the chain which has a valid cache
                    for i in range(len(stack) - 1, 0, -1):
                        validly_cached_node = stack[i]
                        prev_node = stack[i - 1]
                        missing_path_length = cache(validly_cached_node, prev_node) + get_weight(prev_node, validly_cached_node)
                        add_to_results(prev_node, (missing_path_length, validly_cached_node))
                        v2.add((prev_node, validly_cached_node))
                    
                    return cache(curr, prev)
                return cache(curr, prev)
                
            # First-time visit logic
            v1[curr] = prev
            max_length = 0
            nbrs = g[curr]

            for nbr, weight in nbrs:
                if nbr == prev:
                    continue
                length = maxpath(nbr, curr) + weight
                add_to_results(curr, (length, nbr))
                max_length = max(length, max_length)
            v2.add((prev, curr))
            return max_length

        def add_to_results(curr: int, value: tuple):
            if len(results[curr]) < 2:
                results[curr].append(value)
                results[curr].sort(reverse=True)  # Keep sorted with max values first
            else:
                if value > results[curr][-1]:
                    results[curr][-1] = value
                    results[curr].sort(reverse=True)  # Re-sort after replacement

        times = [maxpath(i, i) for i in range(n + 1)]
        return times
157559