3. Radio Waves
There is network of radio-wave devices which can transmit waves of integer frequencies of 1, 2 or 3 units. Two devices can receive messages directly if their transmission frequencies have an absolute difference of 1, at most. The network is given by a tree having network_nodes number of devices and network_nodes - 1 number of edges. The edges are numbered from 1 to network_nodes, in the form of two arrays, network_from, and network_to respectively. There is an undirected edge from network_from[i] to network_to[i] (1 ≤ i < network_nodes). There is also an array of frequency values, frequency, of size network_nodes.
Determine the longest distance between two devices that can transmit their message to each other. A device can transmit a message to another node if there is a simple path such that compatibility values of two consecutive devices differ by no more than one. If no device can transmit a message, return 0.
Note: The distance between two devices is defined as the number of edges in a simple path from one node to the other. A simple path is a sequence of devices from one node to another such that each consecutive device is connected by an edge and no node is used more than once in the sequence.
Example
network_nodes = 4, network_from = [1, 2, 3], network_to = [2, 3, 4], and frequency = [1, 3, 2, 1]
1:12:33:24:1
The graph is labeled device:frequency. Check if a message can be passed for each pair of devices and distance.The graph is labeled device:frequency. Check if a message can be passed for each pair of devices and distance.
• (1, 2): The difference between frequencies, 1 and 3, is greater than 1. A message cannot be transmitted.
• (1, 3): A message cannot be transmitted due to failure at (1, 2).
• (1, 4): A message cannot be transmitted due to failure at (1, 2).
• (2, 3): The difference in frequencies, 3 and 2, is 1. A message can be transmitted.
• (2, 4): Differences are such that a message can be transmitted from 2->3 and 3->4. The distance is 2.
• (3, 4): A message can be transmitted, and the distance is 1.
The longest path, and the answer, is 2.
Function Description
Complete the function calculateMax in the editor below.
calculateMax has the following parameter(s):
int network_nodes: the number of devices
int network_from[network_nodes - 1]: one end of the edge
int network_to[network_nodes - 1]: the other end of the edge
int frequency[network_nodes]: compatibility values for each node.
Returns
int: the longest distance between any pair of devices that can transmit messages to each other
Constraints
• 2 ≤ network_nodes ≤ 2 * 105
• 1 ≤ network_from[i], network_to[i] < network_nodes
• 1 ≤ frequency[i] ≤ 3Sample Input For Custom Testing
STDIN
FUNCTION
4 3
↑↑
network_nodes 4, network_nodes 13 network_from= [1, 1, 1], network_to [2, 3, 4]
12
13
14
4
1
↑↑
frequency [] size network_nodes = 4 frequency = [1, 1, 1, 1]
1
1
1
Sample Output
2 i have this question code but it is giving tle for large inputs so omtimise it or correct it void dfs(int node, int parent, const vector<vector<int>>& adj, const vector<int>& frequency, int current_length, int& max_distance) {
    max_distance = max(max_distance, current_length);
   
    for (int neighbor : adj[node]) {
        if (neighbor != parent) {
            if (abs(frequency[node - 1] - frequency[neighbor - 1]) <= 1) {
                dfs(neighbor, node, adj, frequency, current_length + 1, max_distance);
            }
        }
    }
}

int calculateMax(int network_nodes, vector<int> network_from, vector<int> network_to, vector<int> frequency) {
    vector<vector<int>> adj(network_nodes + 1);
    for (int i = 0; i < network_nodes - 1; ++i) {
        adj[network_from[i]].push_back(network_to[i]);
        adj[network_to[i]].push_back(network_from[i]);
    }

    int max_distance = 0;

    for (int i = 1; i <= network_nodes; ++i) {
        dfs(i, -1, adj, frequency, 0, max_distance);
    }

    return max_distance;
}