### Problem:

1092F - Tree with Maximum Cost

### Problem description:

Given a tree with ** n** vertices, where each vertex has a number

**written on it. Distance between two vertices is defined as the number of edges on the path between them. You have to choose a vertex**

*a*_{i}**such that**

*v***is maximized, where**

*d*_{1}×*a*_{1}+*d*_{2}×*a*_{2}+*d*_{3}×*a*_{3}+ ... ... +*d*_{n}×*a*_{n}**denotes the distance between vertex**

*d*_{i}*i*and vertex

**. You have to print this maximum value.**

*v*### Solution:

Lets ** tot** be the sum of all

**for all vertices**

*a*_{i}**and**

*i***be the sum of all**

*sum*_{i}**of the vertices**

*a*_{j}**in the subtree of vertex**

*j***.**

*i*Now, lets ** subtot_{u}** stores the sum of all

**for all vertices**

*d*_{i}×*a*_{i}**in the subtree of vertex**

*i***, where**

*u***is the distance of vertex**

*d*_{i}**from the vertex**

*i***. But how to calculate the array**

*u***?**

*subtot*Lets root the tree at vertex **1**. If ** u** is a leaf vertex, then it is obvious that

**, since distance from**

*subtot*[*u*] = 0 ×*a*[*u*] = 0**tot**

*u***is 0.**

*u*Now what about the non leaf nodes?

For a vertex v, subtot[v] stores all ** a[i] × d[i]** for all vertex

**i**in the subtree of v. Since for its parent

**, it is 1 distance upper than it's child v, we need to add sum[v] with subtot[v] to get subtot[u], for all child v of u.**

*u*So, for any non leaf vertex ** u**,

**, for all direct child**

*subtot*[*u*] =*subtot*[*v*] +*sum*[*v*]**of vertex**

*v***. Addition of sum[v] is for 1 distance away from child v to parent u.**

*u*So, run a dfs to calculate the array ** sum[]** and

**.**

*subtot*[]**dfs to calculate sum[ ] and subtot[ ]:**

Ok, now if we choose vertex ** u** as the fixed vertex, how to calculate the answer for this vertex?

Notice that, the calculation for any vertex which is in the subtree of vertex ** u** will not change. What will be changed? Other vertices which is not in the subtree of vertex

**. Lets the sum of all subtot[] values of other vertices which are not in the subtree of vertex**

*u***be**

*u***. Every time you go one step down, distance from vertex**

*up***to all other vertices which are not in the subtree of vertex**

*u***will increase by 1. So, wee need to increase**

*u***by**

*up***(we are ignoring the sum[u], since distance to other nodes is increased, which is, sum of all a[i], for all vertex i which are not in the subtree of vertex**

*tot*-*sum*[*u*]**.)**

*u*Then the current answer for vertex ** u** is

**. Here, subtot[u] is for for vertices in the subtree of u, up for vertices which are not in the subtree, tot-sum[u] is for increasing ditance by 1 for non subtree vertices.**

*cur*=*subtot*[*u*] +*up*+*tot*-*sum*[*u*]When you will go to vertex ** v** from vertex

**, then update**

*u***by**

*up***. Here since we are going down, that's why we subtract subtot[v] and sum[v], instead of adding.**

*up*=*cur*-*subtot*[*v*] -*sum*[*v*]Thus, you have to run another dfs to try to choose each vertex as the fixed vertex and keep track of the maximum value ** cur** ans our required answer in

**.**

*ans***2nd dfs to find the max value:**

**Full solution:**

Here is my submission link: 47272565

If you have any further query regarding any part of the solution, feel free to ask in the comment.

I dont know why the Fuck people down-vote this. Even though you know the same solution or there is nothing new in this still he made effort to write a good blog.

So please at least respect someone.

If you dont like blog no need to down-vote just move from here. Literally worst community ever for someone new who want to share something.

it's deserved lots of up-votes <3.

Thank you very much.

Can someone suggest some more problems which use the same concept?

Sum of all Distances Joining Networks Sergey and Subway

Thanks buddy!

May be i have a bit easier and simple solution of this problem.

codedude, can you please explain your dfs1 code??

Please explain this dp[v] = dp[u] + total_sum — 2 * sum[v];

OK, I am going to explain the solution of _abcd_.

In the first dfs, the array sum[] and dp[1] is being calculated. Here sum[i] = sum of all the value of a[] for the nodes which are in the subtree of node i, including the node i itself.

dp[i] = what will be the answer, if we choose node i as our fixed node. Choosing a node i means, what will be the answer if we choose node i and run a dfs from node i.

Hence, dp[1] = what will be the answer, if we choose node 1 as our fixed node. Since the dfs is starting from node 1, if we add d[u]*a[u] to dp[1] for all node u, we will get the value of dp[1]. (Here d[u] means the distance or level of node u.)

Now, the main part is dfs1, the second dfs. When we are going down from node u to node v, what happens? Notice that if we came from node u to node v, it means we already calculated answer for node u in dp[u], which means the answer if we choose node u and run the dfs from node u.

Now what's the change, when we are going to choose node v and calculate answer for this?

When we had chosen u as fixed node, distance or level of node u was 0, level of node v was 1(since it is direct adjacent node of u), similarly level of next nodes adjacent to v was 2, and so on. When we are choosing node v as fixed, then level of node v is 0, nodes directly adjacent to node v is 1 and so on. Therefore level of u will be 1. Similarly, the level of nodes under node v (i.e. in the subtree of v) is decreased by 1 and level of nodes which are not in the subtree of v is increased by 1.

So, when we calculated dp[u], we added all values of nodes down to the node u 1 level more, and for nodes that are not in the subtree of u 1 level less than that of dp[v].

So, if we subtract the sum[v] with dp[u](why sutract? because, we came 1 level down from node u), and add sum of all other a[] of nodes that are not in the subtree of v with dp[u], then we will get dp[v]. Here, sum of all other a[] of nodes that are not in the subtree of v can be calculated by total_sum — sum[v]. (Why add? Because, level of all other nodes that are not in the subtree of v is increased by 1.)

So, dp[v] = dp[u] — sum[v] + (total — sum[v]) = dp[u] + total_sum — 2*sum[v]

Divyansh2 , Mr.Struggler, if you still have any confusion, feel free to comment here. I will try to explain by drawing a tree.

i have not understand the dfs1 part ...could you explain with some more hints..

Suppose the given tree is:

We ran first dfs from node 1.

So, distance of each node is as follows:

d[1]=0,

d[2] = d[3] = d[8] = 1,

d[4] = d[5] = d[6] = d[7] = 2,

So, dp[1] = sum of a[i]*d[i] = 1*0 + 2*1 + 3*1 + 8*1 + 4*2 + 5*2 + 6*2 + 7*2

Now, in dfs1, when we are at node u = 1, and it's child v=3, we will calculate dp[3] using dp[1].

For node v = 3, distance of node 3, d[3] = 0, and

d[6] = d[7] = 1 (previously, for node u=1, d[6] and d[7] was 2, now they are decreased by 1)

d[1] = 1 ((previously, for node u=1, d[1] was 0, now it is increased by 1)

d[2] = d[8] = 2 (previously, for node u=1, d[2] and d[8] was 1, now they are increased by 1)

d[4] = d[5] = 3 (previously, for node u=1, d[4] and d[5] was 2, now they are increased by 1)

So, dp[3] = sum of a[i]*d[i] = 1*1 + 2*2 + 3*0 + 8*2 + 4*3 + 5*3 + 6*1 + 7*1

for dp[1] it was dp[1] = 1*0 + 2*1 + 3*1 + 8*1 + 4*2 + 5*2 + 6*2 + 7*2

What's the difference between dp[1] and dp[3] ? In dp[3], distance of 3, 6 and 7 is decreased by 1 and distance of all other nodes is increased by 1.

So, we ca rewrite dp[3] as dp[3] = 1*(0+1) + 2*(1+1) + 3*(1-1) + 8*(1+1) + 4*(2+1) + 5*(2+1) + 6*(2-1) + 7*(2-1) = 1*0 + 2*1 + 3*1 + 8*1 + 4*2 + 5*2 + 6*2 + 7*2 — (3 + 6 + 7) + (1 + 2 + 8 + 4 + 5)

Here, 1*0 + 2*1 + 3*1 + 8*1 + 4*2 + 5*2 + 6*2 + 7*2 = dp[1]

(3 + 6 + 7) = sum of a[i] in subtree of 3 = sum[3]

(1 + 2 + 8 + 4 + 5) = sum of a[i] of all nodes which are not in the subtree of 3, which can calculated by total_sum — (sum of a[i] in subtree of 3).

So, (1 + 2 + 8 + 4 + 5) = total_sum — sum[3]

, where total_sum = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8

So, dp[3] = dp[1] — sum[3] + total_sum — sum[3] = dp[1] + total_sum — 2*sum[3]

Here, u=1 and v=3

So, for any node u and it's child v:

dp[v] = dp[u] + total_sum — 2*sum[v]

Hope, now it is clear to you !

Divyansh2 and Mr.Struggler hope it will be helpful for you too.

thanks ..i got it :)

Brother, This explanation should be included in blog. It's much simple.

Thank you shahidul_brur. This explanation really helps me.

Thank you very much vaiya

It's really helpful. Thank you sir!

Though I've verified it with pen and paper, still I am so dumb I am not getting it why does it work-

`Since for its parent u, it is 1 distance upper than it's child v, we need to add sum[v] with subtot[v] to get subtot[u], for all child v of u.`

Can you please explain a bit further?Subtot[v] is the summation of all a[i] * d[i] where i denotes all the subtree nodes rooted at v. If u is the parent of v then, to calculate subtot[u], notice that you just need to add 1 to all d[i]s you previously used to calculate subtot[v] as u is 1 distance upper from v. So subtot[u] = sum of all a[i] * (d[i] + 1) which equals a[i] * d[i] + a[i] which is subtot[v] + sum[v], where i is as before.

Wow! Thank you so much Nuwaisir_Rabi. Now, it's crystal clear to me.Oh gosh, How stupid I am to not derive this.Thanks again. Have a good day.

You're welcome!