### MDantas's blog

By MDantas, 7 years ago, ,

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!

• -11

 » 7 years ago, # | ← Rev. 2 →   0 The link below is official website of IOI2012 and it has given hints for the problem Ideal City.Hints for Tasks of IOI2012
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +3 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; } 
•  » » 7 years ago, # ^ |   0 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