Validate a Hierarchy and Compute Propagation Time

Problem Statement

You are given an integer n, representing n servers labeled from 0 to n - 1, and a 2D integer array edges where edges[i] = [parent, child, delay]. This represents a direct communication link where parent transmits updates to child with a latency of delay milliseconds.

An alert system requires all servers to be organized in a valid rooted hierarchy (an arborescence):

1. There must be exactly one designated root server (a server with no incoming edges).
2. Every other server must have exactly one direct parent.
3. All n servers must be reachable from the root server (i.e., no cycles and no disconnected components).

If the configuration forms a valid hierarchy, return the maximum time it takes for an alert triggered at the root to propagate to all reachable servers. If the configuration is invalid, return -1.

Function Signature

def max_propagation_time(n: int, edges: list[list[int]]) -> int:
    pass

Input & Output Format

• Input:
  • n: An integer representing the number of servers.
  • edges: A list of lists, where each inner list contains three integers [u, v, w] denoting a directed edge from u to v with weight w.
• Output:
  • An integer representing the maximum root-to-leaf propagation time, or -1 if the network does not form a valid single-rooted tree.

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• edges[i] = [u, v, w] where 0 <= u, v < n and 0 <= w <= 10^6
• There may be duplicate edges or self-loops in the input.

Examples

Example 1

Input: n = 4, edges = [[0, 1, 2], [0, 2, 5], [1, 3, 4]]
Output: 6
Explanation:
- Server 0 has in-degree 0 (root).
- Server 1 has parent 0, Server 2 has parent 0, Server 3 has parent 1.
- Propagation time to 1 is 2.
- Propagation time to 2 is 5.
- Propagation time to 3 is 2 + 4 = 6.
- All 4 servers are reachable. The maximum propagation time is 6.

Example 2

Input: n = 3, edges = [[0, 1, 3], [1, 2, 2], [2, 0, 1]]
Output: -1
Explanation:
There is a cycle (0 -> 1 -> 2 -> 0) and no node has in-degree 0. Return -1.

Example 3

Input: n = 3, edges = [[0, 1, 2], [2, 1, 3]]
Output: -1
Explanation:
Server 1 has two incoming edges (multiple parents), which violates tree properties. Return -1.