MDantas's blog

Distance Tree
By MDantas, 11 years ago, In English

Hey everyone, I'm solving one of the problems from IOI 2012 ( Ideal City ). I think I've got the whole idea, but my code seems to have some bug as it's not giving the expected output for some cases. I'm not so sure but my guess is that the bug is on the function to calculate the sum between every pair of nodes on a tree, so what I'm asking is if someone knows a specific problem where I can test my function to calculate the sum between every pair of nodes on a tree. If no one knows it, it'd be just good if someone gives me implementation for this specific problem so I can check if mine is correct or near it.

Thanks!

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The link below is official website of IOI2012 and it has given hints for the problem Ideal City.

Hints for Tasks of IOI2012

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You did not understand me. I know how to solve it and I've already coded it, but it has some bug and I don't know where it is. I've a guess that the bug is on the function to calculate the sum between every pair of node on a weighted tree, but I don't know how to test it. So what I'm asking is if some of you guys knows any problem about it.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This snippet should work.

The gist of it is:

  struct Answer{
    ll path_sum;   // sum of all (? -> X) paths toward root
    ll path_count; // quantity of """""""""""""""""""""""""
    ll total;      // answer for subtree rooted at X
  };

  Answer dfs(int x){
    Answer res={0,1,0};

    for (auto e: edge[x]){
      auto rec=dfs(e.id);
      rec.path_sum += e.weight * rec.path_count;

      res = {
        res.path_sum + rec.path_sum,
        res.path_count + rec.path_count,
        res.total + rec.path_sum * res.path_count + rec.total + res.path_sum * rec.path_count
      };
    }
    return res;
  }
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. That's exactly what I was looking for. BTW, the main idea is the same as mine an so the implementation, so I guess the bug is not on this function. Thank you again

    → Reply