Service Thread Counts
MediumTrees · Snowflake
n services are connected as an undirected tree, with services numbered 1 to n and edges[i] = [u, v] meaning services u and v are neighbours.
Assign every service a positive integer thread count such that:
- any two neighbouring services have thread counts that differ by exactly 1, and
- every pair
[node, threads]inknownis respected: servicenodegets exactlythreads.
known is non-empty, and the input is guaranteed to have at least one valid assignment. Among all valid assignments, return the one with the smallest total number of threads, as a list whose i-th element is the thread count of service i + 1. (This minimum assignment is unique.)
Example 1
- Input:
- n = 7, edges = [[1, 2], [2, 3], [2, 4], [4, 5], [5, 6], [5, 7]], known = [[3, 4], [6, 2]]
- Output:
- [2, 3, 4, 2, 1, 2, 2]
- Explanation
- Service 3 is fixed at 4, so service 2 must be at least 3 and services 1 and 4 at least 2. Service 5 can drop to 1, which keeps service 6 at its fixed 2. Service 7 neighbours service 5, so it must be 0 or 2, and 0 is not positive, so it gets 2.
Example 2
- Input:
- n = 4, edges = [[1, 2], [2, 3], [3, 4]], known = [[1, 1]]
- Output:
- [1, 2, 1, 2]
- Explanation
- Service 1 is fixed at the odd value 1, so values alternate odd, even, odd, even along the path. The smallest are 1 and 2.
Example 3
- Input:
- n = 5, edges = [[1, 2], [1, 3], [1, 4], [1, 5]], known = [[2, 5]]
- Output:
- [4, 5, 3, 3, 3]
- Explanation
- Service 2 is fixed at 5, so its neighbour, service 1, must be 4 or 6, and 4 is cheaper. The other leaves must then be 3 or 5, and 3 is cheaper.
Constraints
- 1 ≤
n≤ 105 edges.length==n - 1and the edges form a tree- 1 ≤
known.length≤n, with distinct nodes - 1 ≤
threads≤ 109 - At least one valid assignment exists