Thread Count (Also for Infra Automation Intern)

There are service_nodes of different micro-services in a system with bidirectional connections in the form of a tree, where the i^th edge connects the micro-service service_from[j] and service_to[j]. Each micro-service is configured with a maximum number of live threads that can be present in its lifecycle, where the i^th micro-service can have a maximum of threads[j] threads. The micro-services adjacent to each other must have maximum threads differing by exactly 1. Some configurations were lost, and only k of the micro-services are known. This information is given as a 2D array, currentValues, of size k x 2 denoting [micro-service index, maximum threads], or, [i, threads[i]]. Find the maximum number of live threads that each micro-service can have such that the total number of live threads in the system is the minimum possible. Return an array of length service_nodes where the i^th element denotes the maximum number of live threads for the i^th micro-service. Note: It is guaranteed that the solution always exists.

Constraints

• 1 ≤ service_nodes ≤ 10⁶
• 1 ≤ service_from[i], service_to[i] ≤ service_nodes
• 1 ≤ k ≤ service_nodes
• 1 ≤ currentValues[i][0] ≤ service_nodes
• 1 ≤ currentValues[i][1] ≤ 10⁶

Example 1

Input:

service_nodes = 5
service_from = [1, 2, 3]
service_to = [2, 3, 4]
k = 3
currentValues = [[1, 3], [2, 4], [3, 3]]

Output:

[3, 4, 3, 3]

Explanation: There are 4 micro-services, and 3 edges: {1, 2}, {2, 3}, and {2, 4}. There are 3 configurations left: 1, 2, and 3 with value 3, 4, and 3 respectively on them. The initial configuration is [3, 4, 3, 3], with the maixmum live threads on adjacent micro-services differing by exactly one.