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, lengthi] indicates that there is an undirected edge between nodes ui and vi with a traversal time of lengthi seconds.

You are also given a 0-indexed array disappear, where disappear[i] is the time when node i disappears.

Return an array answer of length n, where answer[i] is the minimum time in seconds it takes to reach node i from node 0 before it disappears. If it’s impossible to reach node i before it disappears, return -1.

Examples

Example 1:

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]
Output: [0,-1,4]
Explanation:
- Node 0: We start at node 0 at time 0, so answer[0] = 0.
- Node 1: We can reach node 1 at time 2, but disappear[1] = 1, so we cannot reach it in time. answer[1] = -1.
- Node 2: We can reach node 2 via path 0 -> 1 -> 2 at time 3, or directly via 0 -> 2 at time 4. Since disappear[2] = 5, we can reach it. The minimum time is 4, so answer[2] = 4.

Example 2:

Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]
Output: [0,2,3]
Explanation:
- Node 0: We start at node 0 at time 0, so answer[0] = 0.
- Node 1: We can reach node 1 at time 2, and disappear[1] = 3, so we can reach it. answer[1] = 2.
- Node 2: We can reach node 2 via path 0 -> 1 -> 2 at time 3, and disappear[2] = 5, so we can reach it. answer[2] = 3.

Example 3:

Input: n = 2, edges = [[0,1,1]], disappear = [1,1]
Output: [0,-1]
Explanation:
- Node 0: We start at node 0 at time 0, so answer[0] = 0.
- Node 1: We can reach node 1 at time 1, but disappear[1] = 1, so we cannot reach it in time (must arrive strictly before disappear time). answer[1] = -1.

Constraints

  • 2 <= n <= 5 * 10^4
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= ui < vi < n
  • 1 <= lengthi <= 10^5
  • disappear.length == n
  • 1 <= disappear[i] <= 10^5

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
BFS / DFS traversal (this problem) O(V+E) O(V) Connectivity, flood fill
Dijkstra O((V+E)log V) O(V) Non-negative edge weights
Union-Find (DSU) O(α(n)) O(n) Dynamic connectivity
Topological sort O(V+E) O(V) DAG ordering, cycle detection

Thinking Process

This is a shortest path problem with time constraints. We need to find the minimum time to reach each node from node 0, but nodes disappear at specific times.

Key Insights:

  1. Dijkstra’s Algorithm: Perfect choice since all edge weights are positive
  2. Disappear Constraint: Check dist[u] + weight < disappear[v] when relaxing edges
  3. Early Termination: If we pop a node with dist[u] >= disappear[u], skip processing its neighbors
  4. Return Format: Use -1 to indicate unreachable nodes or nodes that disappear before we can reach them

Algorithm:

  1. Build adjacency list from edges (undirected graph)
  2. Initialize dist[0] = 0, all others as -1 (or INF)
  3. Use priority queue to process nodes in order of minimum distance
  4. For each popped node u:
    • If dist[u] >= disappear[u], skip (cannot visit)
    • For each neighbor v:
      • Calculate newDist = dist[u] + weight
      • If newDist < disappear[v] and newDist < dist[v] (or dist[v] == -1), update and push
Graph BFS layers S a b t BFS: expand by layers (queue)

Solution Code

Solution 1: Using long long with LLONG_MAX

import heapq

class Solution:
    def minimumTime(self, n, edges, disappear):
        # adjacency list
        adj = [[] for _ in range(n)]
        
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
        
        INF = float('inf')
        dist = [INF] * n
        
        # if start already disappears at time 0
        if disappear[0] == 0:
            return [-1] * n
        
        dist[0] = 0
        pq = [(0, 0)]  # (time, node)
        
        while pq:
            t, u = heapq.heappop(pq)
            
            if t > dist[u]:
                continue
            
            if t >= disappear[u]:
                continue
            
            for v, w in adj[u]:
                nt = t + w
                
                if nt < dist[v] and nt < disappear[v]:
                    dist[v] = nt
                    heapq.heappush(pq, (nt, v))
        
        # build result
        res = [-1] * n
        for i in range(n):
            if dist[i] != INF:
                res[i] = dist[i]
        
        return res

Solution Explanation

Approach: BFS / DFS traversal (this problem)

Key idea: This is a shortest path problem with time constraints. We need to find the minimum time to reach each node from node 0, but nodes disappear at specific times.

How the code works:

  1. Dijkstra’s Algorithm: Perfect choice since all edge weights are positive
  2. Disappear Constraint: Check dist[u] + weight < disappear[v] when relaxing edges
  3. Early Termination: If we pop a node with dist[u] >= disappear[u], skip processing its neighbors
  4. Return Format: Use -1 to indicate unreachable nodes or nodes that disappear before we can reach them
  5. Build adjacency list from edges (undirected graph)
  6. Initialize dist[0] = 0, all others as -1 (or INF)

Walkthrough — input n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5], expected output [0,-1,4]:

  • Node 0: We start at node 0 at time 0, so answer[0] = 0.
  • Node 1: We can reach node 1 at time 2, but disappear[1] = 1, so we cannot reach it in time. answer[1] = -1.
  • Node 2: We can reach node 2 via path 0 -> 1 -> 2 at time 3, or directly via 0 -> 2 at time 4. Since disappear[2] = 5, we can reach it. The minimum time is 4, so answer[2] = 4.

Time Complexity: O((V + E) log V)

  • Building adjacency list: O(E)
  • Dijkstra’s algorithm: O((V + E) log V) with priority queue
  • Total: O((V + E) log V)

Space Complexity: O(V + E)

  • Adjacency list: O(E)
  • Distance array: O(V)
  • Priority queue: O(V)
  • Total: O(V + E)

Key Points:

  • Uses long long to handle large distances
  • Checks t >= disappear[u] after popping to skip nodes that already disappeared
  • Checks nt < disappear[v] when relaxing edges
  • Converts LLONG_MAX to -1 in final result

Solution 2: Using int with -1 (Cleaner)

import heapq
from collections import defaultdict

class Solution:
    def minimumTime(self, n, edges, disappear):
        adj = defaultdict(list)
        
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
        
        dist = [float('inf')] * n
        dist[0] = 0
        
        pq = [(0, 0)]  # (time, node)
        
        while pq:
            du, u = heapq.heappop(pq)
            
            if du > dist[u]:
                continue
            
            for v, w in adj[u]:
                nd = du + w
                
                # must arrive before node disappears
                if nd < disappear[v] and nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        
        return dist

Key Points:

  • Uses int since constraints guarantee values fit in int
  • Uses -1 directly to represent unreachable nodes
  • Checks nd < disappear[v] when relaxing edges
  • Simpler and more readable

    Edge Cases

  1. Node 0 disappears immediately: If disappear[0] == 0, return all -1
  2. Node disappears exactly when we arrive: If arrival_time == disappear[i], return -1 (must arrive strictly before)
  3. Unreachable nodes: Nodes with no path from node 0 return -1
  4. Large edge weights: Edge weights can be up to 10^5, but total path length is bounded by disappear times

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • If dist[u] >= disappear[u], skip (cannot visit)
  • For each neighbor v:
  • Calculate newDist = dist[u] + weight

References

Template Reference

See Graph Templates: Dijkstra for the standard Dijkstra template and variant with node disappearance constraints.