Problem Brief

Radio Waves

INTERNOA

See Snowflake online assessment and hiring insights

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 once. 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.

1Example 1

Input

network_nodes = 4, network_from = [1, 2, 3], network_to = [2, 3, 4], frequency = [1, 3, 2, 1]

Output

Explanation

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.

Constraints

Limits and guarantees your solution can rely on.

na