Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### shahidul_brur's blog

By shahidul_brur, 14 months ago, ,

### Problem:

1092F - Tree with Maximum Cost

### Problem description:

Given a tree with n vertices, where each vertex has a number ai 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 v such that d1 × a1 + d2 × a2 + d3 × a3 + ... ... + dn × an is maximized, where di denotes the distance between vertex i and vertex v. You have to print this maximum value.

### Solution:

Lets tot be the sum of all ai for all vertices i and sumi be the sum of all aj of the vertices j in the subtree of vertex i.

Now, lets subtotu stores the sum of all di × ai for all vertices i in the subtree of vertex u, where di is the distance of vertex i from the vertex u. But how to calculate the array subtot?

Lets root the tree at vertex 1. If u is a leaf vertex, then it is obvious that subtot[u] = 0 × a[u] = 0, since distance from u tot u is 0.

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 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.

So, for any non leaf vertex u, subtot[u] = subtot[v] + sum[v], for all direct child v of vertex u. Addition of sum[v] is for 1 distance away from child v to parent 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 u. Lets the sum of all subtot[] values of other vertices which are not in the subtree of vertex u be up. Every time you go one step down, distance from vertex u to all other vertices which are not in the subtree of vertex u will increase by 1. So, wee need to increase up by tot - sum[u](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 u.)

Then the current answer for vertex u is cur = subtot[u] + up + tot - sum[u]. 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.

When you will go to vertex v from vertex u, then update up by up = cur - subtot[v] - sum[v]. Here since we are going down, that's why we subtract subtot[v] and sum[v], instead of adding.

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.

• +94

 » 14 months ago, # |   +17 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +11
 » 14 months ago, # |   +4 it's deserved lots of up-votes <3.
 » 14 months ago, # |   +4 Thank you very much.
 » 14 months ago, # |   0 Can someone suggest some more problems which use the same concept?
•  » » 14 months ago, # ^ |   +3
•  » » » 14 months ago, # ^ |   +5 Thanks buddy!
 » 14 months ago, # |   0 May be i have a bit easier and simple solution of this problem. codeconst int sz = 2e5 + 2; vector g[sz]; ll dp[sz]; //dp[u] stores sum can uth node could have ll sum[sz]; // sum[u] sum of the subtree of node u including node u ll a[sz]; ll total_sum = 0; int dfs(int u, int level, int par) { dp[1] += level * a[u]; sum[u] = a[u]; for (int v : g[u]) { if (v == par) continue; dfs(v, level + 1, u); sum[u] += sum[v]; } } int dfs1(int u, int par) { for (int v : g[u]) { if (v == par) continue; dp[v] = dp[u] + total_sum - 2 * sum[v]; dfs1(v, u); } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; total_sum += a[i]; } for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0, -1); dfs1(1, -1); ll maxi = -1; for (int i = 1; i <= n; i++) { maxi = max(maxi, dp[i]); } cout << maxi << endl; } 
•  » » 14 months ago, # ^ |   0 dude, can you please explain your dfs1 code??
•  » » 14 months ago, # ^ |   0 Please explain this dp[v] = dp[u] + total_sum — 2 * sum[v];
•  » » » 14 months ago, # ^ |   0 i have not understand the dfs1 part ...could you explain with some more hints..
•  » » » » 14 months ago, # ^ |   0 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*2Now, 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*2What'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 + 8So, 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.
•  » » » » » 14 months ago, # ^ |   0 thanks ..i got it :)
•  » » » » » 14 months ago, # ^ |   0 Brother, This explanation should be included in blog. It's much simple.
•  » » » 14 months ago, # ^ |   0 Thank you shahidul_brur. This explanation really helps me.
 » 14 months ago, # |   +2 Thank you very much vaiya
 » 14 months ago, # |   +2 It's really helpful. Thank you sir!
 » 14 months ago, # |   0 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?
•  » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ |   0 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.
•  » » » » 14 months ago, # ^ |   0 You're welcome!