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.