There are service_nodes of different micro-services in a system with bidirectional connections in the form of a tree, where the ith 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 ith 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 ith element denotes the maximum number of live threads for the ith micro-service.
Note: It is guaranteed that the solution always exists.
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.
1 ≤ service_nodes ≤ 10^61 ≤ service_from[i], service_to[i] ≤ service_nodes1 ≤ k ≤ service_nodes1 ≤ currentValues[i][0] ≤ service_nodes1 ≤ currentValues[i][1] ≤ 10^6
input:
output: