<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 NodeInfo:
    def __init__(self):
        self.child_node = defaultdict(int)
        self.max_tall = 0
        self.max_short = 0

    def add_child(self, node, child_count):
        self.child_node[child_count] += 1
        if child_count > self.max_tall:
            self.max_short = self.max_tall
            self.max_tall = child_count
        elif child_count > self.max_short:
            self.max_short = child_count
    
    def exclusion(self, node, child_count):
        child_count += 2 - int(node % 2)
        total = self.max_tall
        if self.child_node[child_count] == 1 and self.max_tall == child_count:
            total = self.max_short
        return total

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()
        tree = defaultdict(list)
        parents = {}
        def bt(node):
            if node in visited: return
            visited.add(node)

            for n in graph[node]:
                if n in visited: continue
                tree[node].append(n)
                parents[n] = node
                bt(n)

        bt(0)

        below_times = defaultdict(int)
        node_infos = defaultdict(lambda: NodeInfo())

        def below(node):
            if not tree[node]: 
                below_times[node] = 0
                return 0
            if node in below_times: return below_times[node]

            any_even = 1
            fast = -inf
            for n in tree[node]:
                ng = below(n)
                addition = 1 if n % 2 == 1 else 2
                fast = max(fast, ng + addition)
                node_infos[node].add_child(n, ng + addition)

            below_times[node] = fast
            return below_times[node]
        below(0)

        above_times = defaultdict(int)
        def above(node, parent_node_exlusion):
            if node in above_times: return

            p = parents[node]
            pp = 1 if p % 2 == 1 else 2
            node_above_time = parent_node_exlusion + pp
            above_times[node] = node_above_time

            for child in tree[node]:
                child_below = below_times[child]
                node_below_time = node_infos[node].exclusion(child, child_below)
                above(child, max(node_below_time, node_above_time))

        for child in tree[0]:
            child_below = below_times[child]
            addition = node_infos[0].exclusion(child, child_below)
            above(child, addition)

        ans = [0 for _ in range(len(below_times))]
        for k in range(len(ans)):
            ans[k] = max(below_times[k], above_times[k])
        return ans
170871