<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 build_graph(self, edges: List[List[int]]) -> Dict[int, Set[int]]:
        n = 0
        for v,w in edges:
            n = max(n, v+1, w+1)
        graph = {i: set() for i in range(n)}
        for v,w in edges:
            graph[v].add(w)
            graph[w].add(v)
        return graph
    
    def get_info(self, root: int, prev: int) -> int:
        res = []
        for adj in self.graph[root]:
            if adj == prev:
                continue
            time = self.get_info(adj, root)
            time += (1 if adj%2==1 else 2)
            res.append([time, adj])
        res.sort(reverse=True)
        self.info[root] = res[:2]
        return 0 if len(res)==0 else res[0][0]
    
    def dfs(self, root: int, prev: int) -> None:
        res = []
        if prev == -1:
            self.ans[root] = self.info[root]
            for adj in self.graph[root]:
                self.dfs(adj, root)
        else:
            # 1. access to current root's parent node and find a path
            res = []
            dt = 1 if prev%2==1 else 2
            # since we do make sure that we need to mark parent node, if we cannot find longest path through
            # the ans, we just directly access the solo parent node and add the time to the res
            find = False
            for time, node in self.ans[prev]:
                if node == root:
                    continue
                else:
                    find = True
                    res.append([time+dt, prev])
            if not find:
                dt = 1 if prev%2 == 1 else 2
                res.append([dt, prev])
            # 2. append all of its children
            res.extend(self.info[root])
            res.sort(reverse=True)
            self.ans[root] = res[:2]
            for adj in self.graph[root]:
                if adj != prev:
                    self.dfs(adj, root)
            
    
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        self.info = {}
        self.graph = self.build_graph(edges)
        self.ans = {}
        
        self.get_info(0, -1)
        # print(self.info)
        self.dfs(0, -1)
        # print(self.ans)
        
        final_ans = []
        for i in range(len(self.graph)):
            final_ans.append(self.ans[i][0][0])
        
        return final_ans
149571