Блог пользователя dumbhead

SPOJ HOLI
Автор dumbhead, 11 лет назад, По-английски

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.

Теги dfs
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
11 лет назад, # |
← 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.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +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.

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This approach is based on pigeon hole principle.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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?

      → Ответить
      • »
        »
        »
        »
        20 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        if someone visting this blog is also confused about this, hope this helps as it is an old blog.

        Considering an edge we've to look at how much this edge will contribute to our ans.So for each edge the tree will be divided into two parts and in each part there will be x and n-x nodes and if we look for how many people that will travel from this edge will be actually 2 * min(x,n-x).

        Coming to the proof : This is by using pigeonhole principle as if there were x and n-x holes and people are x and n-x as well and every person have to travel so there will have actually min(x,n-x)holes and people are x and n-x so only min(x,n-x) people will travel that edge .so that's why every edge will be traversed exactly 2 * min(x,n-x) times.

        → Ответить