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!

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

sumas the the sum of values of all nodes. Once we remove a nodei, 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 oursumrapidly. 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 thepar[i], we will obviously deletei^{th}node. Now we addval[i] to our answer, and replacepar[i] with a new nodePwhich is a merger ofiandpar[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 removeiwithout 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. Alsopar[i] can be a collection of nodes. You can only deleteiwhenpar[i] is deleted. More would be the time taken to deletepar[i], more would the nodeibe contributing in penalty.the penalty applied would be

val[i] *size[par[i]],and we again replace

par[i] by a new nodePrepresenting 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