### shahidul_brur's blog

By shahidul_brur, 10 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

 » 10 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +11
 » 10 months ago, # |   +4 it's deserved lots of up-votes <3.
 » 10 months ago, # |   +4 Thank you very much.
 » 10 months ago, # |   0 Can someone suggest some more problems which use the same concept?
•  » » 10 months ago, # ^ |   +3
•  » » » 10 months ago, # ^ |   +5 Thanks buddy!
 » 10 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; } 
•  » » 10 months ago, # ^ |   0 dude, can you please explain your dfs1 code??
•  » » 10 months ago, # ^ |   0 Please explain this dp[v] = dp[u] + total_sum — 2 * sum[v];
 » 10 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?