1

Recently I came accross a problem called Gravity Tree I couldn't solve it on my own so I checked the editorial. The authors solution was to dfs over the vertices once and form a segment tree.where each node contains the distance from the vertice to the centre. Then he mentions a second dfs(I don't know what that's doing. I tried printing his data structures, but they totally don't make sense.without knowing what's actually he's trying to do). The language in which he had written was a bit too hard to grasp. I know What are segment trees,dfs,lazy propogation. But I am not able to wrap my head around this solution. And not knowing the solution makes me very anxious and I am not able to concentrate on other things. It would be nice if someone could give a clearer explanation. So that even others who are confused are benifited . thanks in advance :)

The problem setter is adamant.

Harry Jobs
  • 11
  • 2

1 Answers1

0

  1. Do a depth first traversal over the tree from node '1'

    1a.Now as you traverse add the distance from 1 to the nodes being traversed. As well as the distance to the nodes under a node from 1. Let's call this Y1. So for every node there is a Y1 which holds the sum of distance from 1 to itself and its subtree nodes. Also store the sum of squared distance and let's call if Y2. Now additionally we can store the number of elements within the subtree.

All pre processing is done. Now asked force acting on 1 given some node x is turned on we can directly print Y2[x]. But legs say now some other node than 1 say u needs to be calculated. Then compute distance with LCA. Now call this distance d. Now we can modify Y1 by subtracting n times d . and accordingly modify Y2 =Y2-ndd+2Y1*d this is simple math. Hence each query takes log(n) time plus some constant

Dragon Surfer
  • 73
  • 10