Tameshk's blog

By Tameshk, history, 4 weeks ago, In English,

Hi people I've stuck in a well-known hackerrank problem. Comment if you have any idea.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

There is an editorial on hackerrank...

»
4 weeks ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Edit: I realized I missed a fact from the problem statement. So my solution will get TLE. Sorry.

I think there is a "trivial" solution to this. Since the sum of k over all sets is $$$ \le 2 * 10^5$$$, you can use LCA to handle the distance computation. Then just explicitly compute the answer for each set using the given formula.