coding_weeb's blog

How to update all the parent nodes of a child node when you update the child node in a tree ?
By coding_weeb, history, 7 years ago, In English

The value of a node is the product of all the node in its subtree. So how do you update all the parent node when you update the child node ? The original problem is http://codeforces.com/gym/101466/problem/K.

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

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

Auto comment: topic has been updated by coding_weeb (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hint : If you have many continuous SEED queries, how will you solve it?

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

    Oh so I should handle it offline right

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      Keep a list of SEED queries. For each RAND query, the answer is the product of current Tu and every updates on u's children in this list.

      When the list reaches 300 updates, we'll update all the tree with the list in O(n) and clear the list.

      This is not a nice way to solve this problem but i think it's easier to understand.

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

You can construct euler order of tree, so each rooted subtree can be mapped subarray of the order.

If you don't know, what is euler order of graph, there is small summary about it.

  1. Run dfs from root;
  2. Each time when you enter to new node — add it to the end of order;
  3. Each time when you exit node — add it to the end of order;

Let's tin[v] is index of 'enter' v at the order and tout[v] is index of 'exit' v at the order. Then all vertices from T(v) are between tin[v] and tout[v] in order and no other vertices are there.

In converts queries:

  • 'update value in node v' to 'update value at index tin[v]'
  • 'product of all values in the subtree T(v)' to 'product of all values in the subarray tin[v]... tout[v]'

Segment tree or Fenwick tree can handle these queries easily in O(logN).

But for this problem product can be very-very large. Even number of divisors of product can be much more that 64-bit values.

So what we needed here is formula for number of divisors. Let X = p1a1·p2a2...·pmam, where piai are powers of different primes, It can be shown that number of divisors of X is (a1 + 1)·(a2 + 1)...·(am + 1).

We can see that there is guaranteed that all prime divisors of values in problem are  ≤ 13, so there are only 6 different prime divisors could be: (2, 3, 5, 7, 11, 13).

Using this fact, you can solve this problem next way:

  • for each possible prime divisor construct segment/fenwick tree for euler order of graph;
  • each update increases powers of it's prime divisors at index, mapped for updated node;
  • each query collect sums for each prime separately from segment, mapped to subtree, and multiplies them.
→ Reply