shahidul_brur's blog

By shahidul_brur, 5 years ago, In English

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.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you very much.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

code
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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]

    Divyansh.Soni , sajalhsn13, if you still have any confusion, feel free to comment here. I will try to explain by drawing a tree.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 !

        Divyansh.Soni and sajalhsn13 hope it will be helpful for you too.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thank you very much vaiya

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It's really helpful. Thank you sir!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.