Tap here to switch tabs
Problem
Submissions

Problem: Finish Time of Tasks I

Finish Time of Tasks I gives a rooted task tree and a base execution time for each task. Determine the root’s finish time using leaf times and the stated child-based duration rule.

Statement

You are given a tree with nn tasks labeled from 00 to n−1n-1, rooted at node 00. The tree structure is given by a 2D2D integer array edges of length n−1n-1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between task uiu_i and task viv_i.

You are also given an integer array baseTime of length nn, where baseTime[i] represents the base execution time of task ii.

The tasks are executed according to the following rules:

  • If a task is a leaf node (it has no children), its finish time is equal to baseTime[i].

  • If a task has children, let earliest and latest be the minimum and maximum finish times among all its direct children, respectively.

    • The duration of the task itself is calculated as: duration=baseTime[i]+(latest−earliest)\text{duration} = \text{baseTime}[i] + (\text{latest} - \text{earliest}) and the task can only start once all of its children have finished, so its finish time is latest+duration\text{latest} + \text{duration}.

Return the finish time of task 00.

Constraints:

  • 2≤n≤1052 \leq n \leq 10^5

  • edges.length=n−1\text{edges.length} = n - 1

  • edges[i]=[ui,vi]\text{edges}[i] = [u_i, v_i]

  • 0≤ui,vi<n0 \leq u_i, v_i < n

  • baseTime.length=n\text{baseTime.length} = n

  • 1≤baseTime[i]≤1051 \leq \text{baseTime}[i] \leq 10^5

  • The input represents a valid tree rooted at node 00.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Finish Time of Tasks I

Finish Time of Tasks I gives a rooted task tree and a base execution time for each task. Determine the root’s finish time using leaf times and the stated child-based duration rule.

Statement

You are given a tree with nn tasks labeled from 00 to n−1n-1, rooted at node 00. The tree structure is given by a 2D2D integer array edges of length n−1n-1, where edges[i] =[ui,vi]= [u_i, v_i] denotes an undirected edge between task uiu_i and task viv_i.

You are also given an integer array baseTime of length nn, where baseTime[i] represents the base execution time of task ii.

The tasks are executed according to the following rules:

  • If a task is a leaf node (it has no children), its finish time is equal to baseTime[i].

  • If a task has children, let earliest and latest be the minimum and maximum finish times among all its direct children, respectively.

    • The duration of the task itself is calculated as: duration=baseTime[i]+(latest−earliest)\text{duration} = \text{baseTime}[i] + (\text{latest} - \text{earliest}) and the task can only start once all of its children have finished, so its finish time is latest+duration\text{latest} + \text{duration}.

Return the finish time of task 00.

Constraints:

  • 2≤n≤1052 \leq n \leq 10^5

  • edges.length=n−1\text{edges.length} = n - 1

  • edges[i]=[ui,vi]\text{edges}[i] = [u_i, v_i]

  • 0≤ui,vi<n0 \leq u_i, v_i < n

  • baseTime.length=n\text{baseTime.length} = n

  • 1≤baseTime[i]≤1051 \leq \text{baseTime}[i] \leq 10^5

  • The input represents a valid tree rooted at node 00.