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

def search(dic, lit, idx, seen, past):
    total_cost = 0
    # print(lit, idx)
    for i in range(len(lit[idx])):
        new_idx = lit[idx][i]
        if new_idx not in seen:
            # print(new_idx, "new_idx")
            seen.add(idx)
            # if new_idx not in dic[idx]["seen"]:
                # print(new_idx, "new_idx2")
                # dic[idx]["seen"].add(new_idx)
            cost = search(dic, lit, new_idx, seen, idx)
            if new_idx%2==0:
                cost+=2
            else:
                cost+=1
            if  len(dic[idx]["largest"]) < 2:
                dic[idx]["largest"].append([-cost, new_idx])
            else:
                max_val = max(dic[idx]["largest"][0][0], dic[idx]["largest"][1][0])
                if -cost < max_val:
                    if dic[idx]["largest"][0][0] == max_val:
                        dic[idx]["largest"].pop(0)
                        dic[idx]["largest"].append([-cost, new_idx])
                    else:
                        dic[idx]["largest"].pop()
                        dic[idx]["largest"].append([-cost, new_idx])
    
    if len(dic[idx]["largest"]) == 2:
        min_val = min(dic[idx]["largest"][0][0], dic[idx]["largest"][1][0])
        return -min_val
    elif len(dic[idx]["largest"]) == 1:
        return -dic[idx]["largest"][0][0]
    else:
        return 0
        
def serach_all(dic, lit, idx, seen, past):
    total_cost = 0
    # print("idx",idx, "past", past)
    for i in range(len(lit[idx])):
        new_idx = lit[idx][i]
        if new_idx not in seen:
            # print(new_idx, past)
            # print(new_idx, "new_idx")
            seen.add(idx)
            cost = 0

            for j in range(len(dic[idx]["largest"])):
                # print(dic[idx]["largest"][j][1], "opo", idx, "past", past)
                if dic[idx]["largest"][j][1] != new_idx:
                    cost = max(-dic[idx]["largest"][j][0], cost)
            # print(new_idx, "new_idx2")
            # dic[idx]["seen"].add(new_idx)
            # print(new_idx, cost, "cost", past)
            if idx %2==0:
                cost+=2
            elif idx %2!=0:
                cost+=1
            # print(new_idx, cost, "cost")
            if  len(dic[new_idx]["largest"]) <2:
                dic[new_idx]["largest"].append([-cost, past])
            else:
                max_val = max(dic[new_idx]["largest"][0][0], dic[new_idx]["largest"][1][0])
                if -cost < max_val:
                    if dic[new_idx]["largest"][0][0] == max_val:
                        dic[new_idx]["largest"].pop(0)
                        dic[new_idx]["largest"].append([-cost, past])
                    else:
                        dic[new_idx]["largest"].pop()
                        dic[new_idx]["largest"].append([-cost, past])
            serach_all(dic, lit, new_idx, seen, idx)

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:

        lit = [[] for i in range(len(edges)+1)]
        ans = []
        # print(lit)

        for i in range(len(edges)):
            start, end = edges[i]
            lit[start].append(end)
            lit[end].append(start)
        

        dic = {}


        for i in range(len(edges)+1):
            dic[i] = {
                "largest" : [],
                "seen": set()
            }
        seen = set()
        # print(dic)
        ans.append(search(dic, lit, 0, seen, -1))

        seen = set()
        serach_all(dic, lit, 0, seen, 0)
        for i in range(1, len(edges)+1):
            if len(dic[i]["largest"]) ==1:
                ans.append(-dic[i]["largest"][0][0])
            else:
                max_val = max(-dic[i]["largest"][0][0], -dic[i]["largest"][1][0])
                ans.append(max_val)
        # print(dic)
        
        
        return ans


        
165546