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

Автор oversolver, 4 года назад, По-английски

Given a rooted tree.

Suppose query (v,d) is set of vertices in subtree of v in depth d from v.

Let's take all possible queries and leave only distinct sets.

Sum of sizes of these sets is $$$O(n\sqrt{n})$$$.

Actually, idk how to prove it. If you know proof, please post it here.

I met it in one Gerald's lecture with proof like "try to construct worst case and you see it".

I can construct such family of trees with $$$f(k)\approx \frac{n \sqrt n}{2}$$$ where $$$n(k) = \frac{k(k+1)}{2}$$$

Here tree with k=4:

Only two times I tried to apply this as base of my solutions. But it was 1) useless — there are was easiest ones 2) painfull.

If you have some problems for this feature, post it please.

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

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

Wrong

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Consider tree as [bamboo] + [star in bottom]:

    edges (1,2), (2,3), ... ,(n/2-1,n/2) and (n/2,n/2+1), (n/2,n/2+2), ..., (n/2,n)

    lowest array in height n/2 has size more than $$$\sqrt{n}$$$

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

Maybe smth like this. Lets calculate for every vertex $$$v$$$ number of distinct sets containing it. Assume we are checking set $$$(p, d)$$$. If we want to count $$$v$$$, set $$$(p, d)$$$ must differs from set $$$($$$ancestor of $$$v$$$ on dist $$$d - 1, d - 1)$$$. So there at least should exists path of length $$$d$$$ starting in $$$p$$$ such that it`s second vertex is not ancestor of $$$v$$$. So every vertex can lie only in $$$\mathcal{O}(\sqrt n)$$$ such sets.