babjamal's blog

Asking for help to solve a Data Structure related tree problem
By babjamal, history, 33 hours ago, In English

Recently I have come across a problem of an IUPC contest, where the problem asks for the summation of the mex value of all subtrees of a tree for each vertex where the vertex is the root of the tree. The detailed statement is given below or can be found in I-Mexy.

Statement

Can anyone give me hints or provide any resources about this topic?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
33 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

You can do this with Small-to-Large merging in O(N * log^2 N) time, search on USACO Guide for small-to-large there is a topic.

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

    OK I have been able to solve the problem using this technique for a single rooted tree. But what about to solve the problem for each root/vertex?

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

      Oh, I didn't read that part of the problem, my bad I thought it was for a single root only!

      → Reply
»
29 hours ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

probably it can be (over)solved by root rotating and mex on segment queries.

supporse we know mex for each subtree initially (root=0). if r is root and c its child we can rotate this edge to make c as root. how will mexes change? mex(c) will be mex of all numbers and mex(r) will be mex of numbers except subtree of c (current subtree)

so current subtree is defined by oriented edge. in tree with root 0 this will be subtree or... undertree (how to call it better?). if we concate euler tour of tree twice than both subtree and undertree becomes segment. and we can ask mex on segment in O(logn).

upd (I got AC). ok we need only mex of each subtree (for init) and mex for each not subtree (for rotating). this can be found somehow easy or by mex on segments query (O(qlogn)).

→ Reply