Tree Broadcast Time

SilverShow difficulty

10000ms500MBNov 15, 2026

You are given a rooted tree with n nodes labeled from 0 to n - 1. The root is node root. For every other node i, its parent is parent[i]. The root has parent[root] = -1.

A message starts at the root at minute 0. When node i receives the message, it waits delay[i] minutes and then passes the message to all of its children at the same moment. Each child then does the same for its own children.

Return the number of minutes until every node has received the message.

You can assume parent describes a single tree rooted at root. Note that a node with no children always has delay[i] = 0.

Examples

Example 1

Input: n = 1, root = 0, parent = [-1], delay = [0]
Output: 0
Explanation: The root is the only node. It has the message at minute 0.

Example 2

Input: n = 6, root = 2, parent = [2,2,-1,2,2,2], delay = [0,0,1,0,0,0]
Output: 1
Explanation: Node 2 is the root and the parent of every other node.
It passes the message to all five children after delay[2] = 1 minute.

Example 3

Input: n = 7, root = 0, parent = [-1,0,0,1,1,2,2], delay = [1,2,5,0,0,0,0]
Output: 6
Explanation: Node 0 passes the message to nodes 1 and 2 at minute 1.
Node 1 passes it to nodes 3 and 4 at minute 1 + 2 = 3.
Node 2 passes it to nodes 5 and 6 at minute 1 + 5 = 6.
The last nodes receive it at minute 6.

Constraints

$1 \leq$ n $\leq 10^5$
$0 \leq$ root $<$ n
parent.length $=$ delay.length $=$ n
$0 \leq$ parent[i] $<$ n for every i other than root
parent[root] $= -1$
$0 \leq$ delay[i] $\leq 1000$
delay[i] $= 0$ if node i has no children
parent describes a single tree rooted at root

Loading editor...

Samples 3

Custom 0

sample

Include in Run

n =integer

root =integer

parent =int[]

delay =int[]

Expected

Examples

Example 1

Input: n = 1, root = 0, parent = [-1], delay = [0] Output: 0 Explanation: The root is the only node. It has the message at minute 0.

Example 2

Input: n = 6, root = 2, parent = [2,2,-1,2,2,2], delay = [0,0,1,0,0,0] Output: 1 Explanation: Node 2 is the root and the parent of every other node. It passes the message to all five children after delay[2] = 1 minute.

Example 3

Input: n = 7, root = 0, parent = [-1,0,0,1,1,2,2], delay = [1,2,5,0,0,0,0] Output: 6 Explanation: Node 0 passes the message to nodes 1 and 2 at minute 1. Node 1 passes it to nodes 3 and 4 at minute 1 + 2 = 3. Node 2 passes it to nodes 5 and 6 at minute 1 + 5 = 6. The last nodes receive it at minute 6.