README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Hard	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3241.Time%20Taken%20to%20Mark%20All%20Nodes/README_EN.md	2521	Biweekly Contest 136 Q4	Tree Depth-First Search Graph Dynamic Programming

3241. Time Taken to Mark All Nodes

中文文档

Description

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.

Initially, all nodes are unmarked. For each node i:

• If i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.
• If i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.

Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.

Note that the answer for each times[i] is independent, i.e. when you mark node i all other nodes are unmarked.

 

Example 1:

Input: edges = [[0,1],[0,2]]

Output: [2,4,3]

Explanation:

• For i = 0:

  <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>
  

Example 2:

Input: edges = [[0,1]]

Output: [1,2]

Explanation:

• For i = 0:

  <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>
  

Example 3:

Input: edges = [[2,4],[0,1],[2,3],[0,2]]

Output: [4,6,3,5,5]

Explanation:

 

Constraints:

• 2 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• The input is generated such that edges represents a valid tree.

Solutions

Solution 1

Python3

Java

C++

Go