Блог пользователя aakarshmadhavan

Find sum of distances in undirected tree
Автор aakarshmadhavan, история, 6 лет назад, По-английски

I just need some very basic hints.

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

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just use LCA.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I thought about advancement in this question. What if instead of a tree it is a connected graph with cycles allowed? 1<=N<=200000

Any help would be helpful?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The sum of depth of node is equal to the sum of subtree size of node.

so you maybe just need to use change root DP to solve it in $$$O(n)$$$.

the code
→ Ответить