dumbhead's blog

By dumbhead, 5 years ago, In English,

I was trying this problem HOLI but I am not able to come up with a good solution. I was thinking of pairing up the leaf nodes of the longest path in the tree. After pairing up, I remove the two paired nodes and continue with the next longest path. But this would give a O(n^2) approach resulting TLE. Can somebody tell me an efficient approach for the solving problem ? I would be happy if somebody helps me in this. Thank you in advance.

Tags dfs
 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
5 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The idea is the following:

Let's take a look at one edge of the tree. If this edge is removed, there are two sub-trees instead of the initial tree. Let's assume that one of these sub-trees contains x vertices. Then there're exactly y = n — x vertices in another sub-tree. There're at most 2 * min(x, y) paths going through this edge. So all we need to know is how many vertices there are in each of two sub-trees if this edge is removed. (For edge i, let it be x[i] and y[i]) It's clear that the answer is the sum for all edges: 2 * min(x[i], y[i]) * weight[i] (weight[i] — weight of the i-th edge).

There's only one thing left to do to solve the problem: calculate x[i] and y[i] for all edges quickly. It can be done with simple sub-tree dp(we need to know the number of vertices in a sub-tree). This solution works in O(N) and it's pretty simple to implement. Here's my code.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you for the reply. Can you please explain how did you get that there're at most 2 * min(x, y) paths going through an edge ? I am not getting this part.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Let's assume that for i-th edge x[i] > y[i]. If more than y[i] paths go through this edge, there'll be y[i] houses for people to stay in and more than y[i] people. So they will have to share a house.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes, I got it. The problem really simplifies a lot after this deduction which is not trivial. Got it accepted with this approach. Thanks a lot for the help.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      pigeonhole principle

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey wanted to know how u came up with the idea