OA problem help

Правка en1, от Aspergillus, 2024-07-20 13:07:19

Hi the following was asked by Adobe on an OA a day ago. The OA is over.

You are given a tree of n nodes and each node has a number associated with it. These numbers range from 1 to n, inclusive. You have to output the number of edges which if removed, makes the maximum frequency of a node value of both the resulting trees to be <= k. k is given and is <= n. The value of n goes upto 1e5.

I tried dfsing the frequency but soon realised I cant have the frequency of each subarray without storing them somewhere, which obviously wouldnt work due to both MLE and TLE. Please help!

Теги graph, tree, frequency array, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Aspergillus 2024-07-20 13:07:19 602 Initial revision (published)