strange14's blog

MEX from root node to every other node in a tree
By strange14, history, 3 years ago, In English

Given a rooted tree having N nodes. Root node is node 1. Each ith node has some value , val[i] associated with it.

For each node i (1<=i<=N) we want to know MEX of the path values from root node to node i.

MEX of an array is smallest positive integer not present in the array, for instance MEX of {1,2,4} is 3

Example : Say we are given tree with 4 nodes. Value of nodes are [1,3,2,8] and we also have parent of each node i (other than node 1 as it is the root node). Parent array is defined as [1,2,2] for this example. It means parent of node 2 is node 1, parent of node 3 is node 2 and parent of node 4 is also node 2.

Node 1 : MEX(1) = 2 Node 2 : MEX(1,3) = 2 Node 3 : MEX(1,3,2) = 4 Node 4 : MEX(1,3,8) = 2 Hence answer is [2,2,4,2]

In worst case total number of Nodes can be upto 10^6 and value of each node can go upto 10^9.

Can anyone tell the optimal way to solve this problem?

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

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

you can use set, in the beginning there are every number from 1 to N + 1. When you go from node V to node U, you remove val[U] from the set, and the answer for U is the smallest number in the set. When you come back from U to V, you check if there is no Z in the path from root to V such as val[Z] == val[U], you insert val[U] in the set.

Time complexity is O(N log N)

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

Flatten the tree start from root start adding nodes in dfs order, maintain a fenwick tree or set as mentioned in the first comment for mex.

There is a more general version of this problem Frank Sinatra problem F in which you have to answer mex on the path from node u to v which can be solved similarly offline.

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

There is a $$$O(n)$$$ solution. The main idea is using a linked list instead of set/fenwick tree.

Keep a linked list represents the numbers not appeared in the path from root to current node $$$x$$$. Assume we now arrive at a child of $$$x$$$, named it $$$y$$$. If $$$val[y]$$$ is the first time to appear, we remove it from the linked list. In order to check if it has appeared before, just maintain a auxiliary array cnt, cnt[x] means the number $$$x$$$ has occurred cnt[x] times.

When we go back, we just apply a undo operation, instead of insert. With a stack we can solve the problem.

(If there is something wrong with my solution, pls tell me as soon as possible)

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

    Is your cnt just a usual array? Then I doubt it can be of size 1e9. If it is a hash map then it is O(n), but I would better do O(n log n) with usual map.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      The MEX can never be greater than $$$n + 1$$$, so we can ignore values greater than $$$n + 1$$$, making the cnt array size $$$n + 1$$$ (and same for the linked list).

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

You can maintain bitwise trie

When you add some value $$$a_v$$$, you add this value in trie and in each node you need calc count of used leafs. When you find the answer for node, you go to some leaf in trie. If left subtree have all leafs, you go to right subtree

→ Reply