By dumbhead, 7 years ago, ,

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.

• +6

 » 7 years ago, # | ← Rev. 2 →   +7 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.
•  » » 7 years ago, # ^ |   +5 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.
•  » » » 7 years ago, # ^ |   +6 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.
•  » » » » 7 years ago, # ^ |   +5 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.
•  » » » 15 months ago, # ^ |   0 pigeonhole principle
•  » » 19 months ago, # ^ |   0 hey wanted to know how u came up with the idea
 » 3 months ago, # |   0 It may be a silly doubt but are we sure doing c = 2 * (x, n — x) * weight will give max? Will we always find a configuration as I m thinking what if due to max contribution c of some edge, max contribution of some other edge may reduce.
•  » » 2 months ago, # ^ |   0 This approach is based on pigeon hole principle.
•  » » » 2 months ago, # ^ |   0 What he is asking is how to prove there always exists a configuration (or pairing) in which every edge gets traversed exactly $2 \cdot \min(x, n - x)$ times.Does someone have a nice proof for this?