<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 TreeNode:
  def __init__(self, val):
    self.val_ = val
    self.children_ = []
    self.height_ = []
  
  def add_child(self, child):
    self.children_.append(child)

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
      tracker = defaultdict(set)
      n = 0
      for src, tar in edges:
        tracker[src].add(tar)
        tracker[tar].add(src)
        n = max(n, src)
        n = max(n, tar)

      #construct tree
      root = TreeNode(0)
      start = [root]
      visited = set()
      visited.add(0)
      while start:
        new_start = []
        for element in start:
          for child in tracker[element.val_]:
            if child not in visited:
              visited.add(child)
              tempnode = TreeNode(child)
              element.add_child(tempnode)
              new_start.append(tempnode)
        start = new_start
      
      def check_tree(startnode):
        start = [startnode]
        while start:
          current = []
          new_start = []
          for element in start:
            current.append(element.val_)
            for child in element.children_:
              new_start.append(child)
          start = new_start
          print(current)


      def change_tree(node):
        if not node.children_:
          return 0
        else:
          for element in node.children_:
            temp_res = change_tree(element)
            node.height_.append(temp_res + 1)
            if element.val_ % 2 == 0: node.height_[-1] += 1
          return max(node.height_)
      
      change_tree(root)

      final = defaultdict(int)
      def calc_tree(node, carryon, res):
        if node.height_:
          res[node.val_] = max(max(node.height_), carryon)
        else:
          res[node.val_] = carryon
        
        if node.height_:
          addon = 1
          if node.val_ % 2 == 0: addon += 1
          maxi = max(node.height_)
          for i in range(len(node.children_)):
            if node.height_[i] != maxi:
              calc_tree(node.children_[i], maxi + addon, res)
            else:   addon = 1
          if node.val_ % 2 == 0: addon += 1
          maxi = max(node.height_)
          counter = node.height_.count(maxi)
          second_maxi = -sys.maxsize
          for element in node.height_:
            if element != maxi:
              second_maxi = max(second_maxi, element)
          maxi = max(maxi, carryon)
          second_maxi = max(second_maxi, carryon)
          for i in range(len(node.children_)):
            if node.height_[i] != maxi:
              calc_tree(node.children_[i], maxi + addon, res)
            else:
              if counter == 1:
                calc_tree(node.children_[i], second_maxi + addon, res)
              else:
                calc_tree(node.children_[i], maxi + addon, res)
      
      calc_tree(root, 0, final)
          
      return [final[i] for i in range(n+1)]
      
145578