Change Segment Colors
Updated
Problem statement
There is a map with n segments. Every segment on the map can either be a red segment or a black segment.
There is no circle(closed loop) in the map. Initially, all segments on the map are red segments. You need to perform m
operations on the map, and there are two types of operations:
- Given two stations
aandb. First, for every stationxon the path fromatob(includingaandb), you should change all segments connected toxinto red segments. Then, convert all the segments on the path fromatobinto black segments. - Given two stations
aandb, you need to calculate how many black segments there are on the path fromatob.
Input Format:
- The input is an array of string.
- The first string contains two integers
nandm, wherenrepresents the number of stations andmrepresents the number of operations. - The next
n - 1strings, each string contains two integersuandv, indicating there is a segment between stationuand stationv. - The next
mstrings, each string contains integersopi,aiandbi.opirepresents an operation:opi=1means the first operation, andopi=2means the second operation.aiis not equal tobi.
Output Format:
The output is an array of integer. For every second type of operation, output an integer as the answer.
Function
changeSegmentColors(operations: String[]) → int[]Examples
Example 1
operations = ["8 5", "1 2", "1 3", "3 4", "4 5", "4 6", "2 8", "2 9", "1 1 6", "1 2 4", "2 1 6", "1 1 5", "2 2 6"]return = [2, 2]For the first operation (1 1 6), the path from station 1 to station 6 is changed to black segments. For the second operation (1 2 4), the path from station 2 to station 4 is changed to black segments. For the third operation (2 1 6), the number of black segments on the path from station 1 to station 6 is 2. For the fourth operation (1 1 5), the path from station 1 to station 5 is changed to black segments. For the fifth operation (2 2 6), the number of black segments on the path from station 2 to station 6 is 2.
More Trend Micro interview questions
Similar questions at other companies
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Sum Dynamic Weighted Tree DistancesJuspay · OA
- Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
- Part 1: The Narrowest KeyScale AI · OAScale AI interview questions
- Longest Transfer Time in a Server TreeRippling · OARippling interview questions
- Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
- Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions