aakarshmadhavan's blog

By aakarshmadhavan, history, 4 months ago, In English,

I just need some very basic hints.

I am thinking of topological sort + BFS to start. What do you say? (No spoilers plz)

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Lets say you know the sum of distances from a node. Think about what happens to the sum if you go to a child or to the parent.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, I am not sure I understand your hint.

    If I know the sum of distances node X to node Y I am not sure how this helps? Thanks!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He meant that, if for some node u, you know ans[u] then what happens to ans[v] if v is a child/parent of u. There isn't too much difference between ans[u] and ans[v], can you figure that out?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just use LCA.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Simple dfs would be much easier and probably faster.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm. That works if he is looking for distance from a single node to the rest of the nodes. What if i is arbitrary?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just do dfs for all vertices, n^2 should pass for given constraints.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh yeah. You are right. I didn't note the small constraints.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but some judges have insanely tight time limits, maybe it will not be fast enough still

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you help me with DFS approach in O(N)? I am very confused how to do it. Thank you so much

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

yes, topological sort + bfs can be done, but it's easier and faster to just use a DFS traversal. You can remember, in the recursive function, the depth that you are currently at, and just add that to the answer. When you go to your children, increase the depth argument. This is O(n), so when you do a new traversal for every node, it will be O(n^2).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you help me out with this DFS approach? I am trying to understand it properly. Say I do a DFS from Node X to all of its children, then if denote:

    DP[x][some child] = DP[some child][x] = distance from X to some Child, which ever child we are looking at.

    Are you saying I should then use DP[x][some child] for parents of node X?

    Thanks!

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I'm saying you don't have to store it in memory.


      int sum = 0; bool visited[MAXN]; void dfs(int u, int depth) { visited[u] = true; sum += depth; for(int v : neighbours[u]) { if(!visited[v]) { dfs(v, depth + 1); } } }

      So, when you do dfs(x, 0); the variable sum will hold the solution for that node, calculated in O(n). Cheers.