rachitiitr's blog

By rachitiitr, history, 7 years ago, In English

Hello Codeforces Community,
I found this problem very interesting, but couldn't solve it. Also the editorial wasn't clear to me. What I was trying was a greedy solution that passed half of the test cases.

Problem Tags: Trees, dsu
Could someone explain it in a better way?
Thanks!

  • Vote: I like it
  • +18
  • Vote: I do not like it

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

The editorial was most probably written in some other language and wrapped up via Google Translator. Anyway, I have finally started building the intuition how dsu will give the right answer. Before reading my explanation, you should read the editorial mentioned above once.
Let's denote sum as the the sum of values of all nodes. Once we remove a node i, a penalty of value (sum - val[i]) is applied, and,

sum = sum - val[i]
ans = ans + sum - val[i]

This adds more options for us to remove nodes (the children of node $i$ become available). Now overall aim is to perform removal operations to minimize ans.
Having said this, the layman's approach would be to remove the node with highest val[i], and decrease our sum rapidly. This is obviously partially correct, but the greedy intuition can be organised to give the correct answer.
Consider the node with highest val[i]. Whenever we remove the par[i], we will obviously delete ith node. Now we add val[i] to our answer, and replace par[i] with a new node P which is a merger of i and par[i].

size[P] = 2, val[P] = val[i] + val[par[i]]....(1)

Now $P$ has absorbed the property in itself that once you remove par[i], you then also remove i without any delay. Thus we select nodes greedily and form components to tell that once the root of that component is selected, the other nodes in the components should be deleted right away.

Now keep in mind that when you are deleting a node i, it might not be a single node, but a collection of nodes. Also par[i] can be a collection of nodes. You can only delete i when par[i] is deleted. More would be the time taken to delete par[i], more would the node i be contributing in penalty.
the penalty applied would be val[i] * size[par[i]],
and we again replace par[i] by a new node P representing the merger of these two components and this allows us to correctly add the penalty terms when the parent of this new component would be deleted.
Note that since we are merging components, equation (1) would change a lil bit.
I hope I was clear enough. It seems convincing to me now :D