<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 SegmentTree:
    def __init__(self, length):
        self.DEFAULT = 0
        self.length = length
        self.segtree = [self.DEFAULT] * (2 * length)

    def f(self, a, b):
        return max(a, b)

    def set(self, ind, val):
        ind += self.length
        self.segtree[ind] = val
        while ind > 1:
            ind //= 2
            self.segtree[ind] = self.f(self.segtree[2 * ind], self.segtree[2 * ind + 1])

    def range(self, start, end):
        res = self.DEFAULT
        start += self.length
        end += self.length
        while start < end:
            if start % 2 == 1:
                res = self.f(res, self.segtree[start])
                start += 1
            if end % 2 == 1:
                end -= 1
                res = self.f(res, self.segtree[end])
            start //= 2
            end //= 2
        return res


class Solution:
    def dfs(self, i, par, adj, times, dp):
        for x in adj[i]:
            if x != par:
                self.dfs(x, i, adj, times, dp)
                if x % 2 == 0:
                    dp[i] = max(dp[i], dp[x] + 2)
                else:
                    dp[i] = max(dp[i], dp[x] + 1)

    def reroot(self, i, par, adj, times, dp, except_dict):
        times[i] = dp[i]
        for x in adj[i]:
            if x != par:
                lastdp1, lastdpx = dp[i], dp[x]
                dp[i] = except_dict[(i, x)]
                if i % 2 == 0:
                    dp[x] = max(dp[x], dp[i] + 2)
                else:
                    dp[x] = max(dp[x], dp[i] + 1)
                self.reroot(x, i, adj, times, dp, except_dict)
                dp[i], dp[x] = lastdp1, lastdpx

    def make_except(self, i, par, adj, except_dict, dp):
        anss = [(x, dp[x]) for x in adj[i]]
        seg = SegmentTree(len(anss))
        for j, (f, s) in enumerate(anss):
            if f % 2 == 0:
                seg.set(j, s + 2)
            else:
                seg.set(j, s + 1)
        
        for j, (f, s) in enumerate(anss):
            mxx = seg.range(j + 1, len(anss))
            mxx = max(mxx, seg.range(0, j))
            except_dict[(i, f)] = mxx

        for x in adj[i]:
            if x != par:
                lastdpi, lastdpx = dp[i], dp[x]
                dp[i] = except_dict[(i, x)]
                if i % 2 == 0:
                    dp[x] = max(dp[x], dp[i] + 2)
                else:
                    dp[x] = max(dp[x], dp[i] + 1)
                self.make_except(x, i, adj, except_dict, dp)
                dp[i], dp[x] = lastdpi, lastdpx

    def timeTaken(self, edges):
        n = len(edges) + 1
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        times = [0] * n
        dp = [0] * n
        self.dfs(0, -1, adj, times, dp)
        except_dict = {}
        dpc = dp[:]
        self.make_except(0, -1, adj, except_dict, dpc)
        self.reroot(0, -1, adj, times, dp, except_dict)
        return times
169540