FastPrep

Description

Solutions

Get Minimum Servers

🔥 FULLTIME📚RELATED PROBLEMS

In a neural network, there are nodes representing servers capturing neural signals in a cutting-edge machine learning application. Akin to the architecture of a neural network, there are server_nodes servers, where the ith server captures the signal of minimum neural activity represented by minActivity[i]. The servers are connected in a tree structure with server_nodes - 1 connections, where the ith connection connects the servers server_from[i] and server_to[i] and the change in neural activity of the signal traveling the ith connection is represented by server_weight[i].

The neural activity of a signal transmitted from server x and reaching server y is the sum of the neural activity change by traveling across the path from x to y.

Note:

All the servers transmit the signals of activity 0.

The tree is rooted at server 1.

It is possible for a signal to have negative neural activity as well.

The neural activity of a signal after passing through a connection improves or deteriorates, depending on whether the server_weight[i] is positive or negative respectively.

A server u is said to be vulnerable if there exists a server v (!= u) in the subtree of u such that:

The neural activity of the signal reaching server v from server u is greater than minActivity[v].

Note: A subtree of a node x is a tree containing all the children of x and having x as the root.

The server can be disconnected in the following way:

Choose a leaf node from the remaining tree and remove that server.

The task is to determine the minimum number of servers that need to be disconnected such that no server remains vulnerable.

Function Description

Complete the function getMinServers in the editor.

getMinServers has the following parameters:

int server_nodes: the number of servers
vector server_from: the server from which the signal is sent
vector server_to: the server to which the signal is sent
vector server_weight: the change in neural activity due to the signal passing through the server
vector minActivity: the minimum neural activity that a server can handle without being vulnerable

Returns

int: the minimum number of servers that need to be disconnected

Example 1:

Input:  server_nodes = 5, server_from = [1, 1, 3, 3], server_to = [2, 3, 4, 5], server_weight = [-2, 5, -5, -3], minActivity = [0, -10, 5, -5, 5]
Output: 2 
Explanation:
  
   
Server 1 is vulnerable as the neural activity of signal reaching server 4 from 1 has an activity of 0(>-5). So server 4 is removed.
    
Server 1 is vulnerable as the neural activity of signal reaching server 2 from 1 has an activity of -2(>-10). So server 2 is removed.
     
Hence, the answer is 2.

Example 2:

Input:  server_nodes = 4, server_from = [1, 1, 2], server_to = [2, 3, 3], server_weight = [3, 4], minActivity = [1, 2, 3, 4]
Output: 1 
Explanation:

In this case, you need to disconnect at least one server to ensure no server is vulunerable.

Constraints:

3 ≤ server_nodes ≤ 2 * 10^5 1 ≤ server_from[i], server_to[i] ≤ server_nodes -10^9 ≤ server_weight[i] ≤ 10^9 -10^9 ≤ minActivity[i] ≤ 10^9