<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 timeTaken(self, edges: List[List[int]]) -> List[int]:
        """
        rerooting, n2 not possible
        
        same as height of all roots with edge len of 1/2
        """
        #print("---")
        n=len(edges)+1
        adj=defaultdict(list)       #undirected
        newAdj=defaultdict(list)    #directed
        INF=10**20
        for a,b in edges:
            adj[a].append(b)
            adj[b].append(a)
            
        dp=[None for _ in range(n)] #subproblem at subtree
        def dfs(i):
            res=0
            for nei in adj[i]:
                if nei not in visited:
                    visited.add(nei)
                    newAdj[i].append(nei)
                    res=max(
                        res, 
                        dfs(nei) + (1 if nei&1 else 2) 
                    )
            #print("dfs ", i, res)
            dp[i]=res
            return res
        
        # for i in range(n):
        #     visited=set()
        #     visited.add(i)
        #     print(i, dfs(i))
        visited=set()
        visited.add(0)
        dfs(0)
        #print(newAdj)
        adj=newAdj  #use directed easier
        
        ans=[0 for _ in range(n)]
        def dfs2(i, parentSideMax, p): #parentSideMax: at perspective of i
            if p is None:
                curParentSideMax = 0
            else:
                curParentSideMax = parentSideMax + (1 if p&1 else 2)
                
            ans[i]=max(
                curParentSideMax, 
                dp[i]   #subproblem at subtree i
            )
            
            m=len(adj[i])
            #pre/siffix perspective: next node
            prefix=[0 for _ in range(m)]       #for computing max(dp[j] for j in nei) excluding particular nei
            suffix=[0 for _ in range(m)]        #need exclude parent too
            for j,nei in enumerate(adj[i]):
                prefix[j]=max((1 if nei&1 else 2) + dp[nei], prefix[j-1] if j>0 else 0)
            for j in range(m-1,-1,-1):
                nei=adj[i][j]
                suffix[j]=max((1 if nei&1 else 2) + dp[nei], suffix[j+1] if j<m-1 else 0)
                    
            for j,nei in enumerate(adj[i]):
                if nei not in visited:
                    visited.add(nei)
                    
                    childSideMax= max(prefix[j-1] if j>0 else 0 , suffix[j+1] if j<m-1 else 0)#excluding the child we're going to
                    
                    newParentSideMax = max(
                        curParentSideMax,
                        childSideMax
                    )
                    dfs2(nei, newParentSideMax, i)
        
        visited=set()
        visited.add(0)
        dfs2(0, 0, None)
        return ans
        
            
            
144246