Hi,

Consider a rooted tree

** size(v)** = number of vertices in subtree of v

Any good limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i)}$$$ ?

like

$$$O(n \log n)$$$

$$$O(n \log \log n)$$$

$$$O(n)$$$

...

**UPD :**

** b(v)** is a son of v with the largest subtree size.

limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i) - size(b(i))}$$$ ?

$$$O(n\sqrt{n})$$$ ofc, consider a bamboo, $$$\sum\limits_{i = 1}^{n}{\sqrt{i}} \ge \frac{n}{2}\sqrt{\frac{n}{2}}$$$

Informally speaking, it should be true for any rooted tree that $$$\sqrt{n-1} \leq \sum\limits_{i=1}^{n} \sqrt{size(i)} \leq \binom{n}{2}$$$, as $$$0 \leq size(i) \leq n-1$$$ for any vertex $$$i$$$, and there are two corner cases:

If each vertex has exactly one child, then the tree height is $$$n-1$$$. The size function starting from the leaf vertex is the algebraic series: $$$0, 1,\ldots,n-1$$$, and $$$\sum\limits_{i=1}^{n} \sqrt{size(i)} = \sum\limits_{i = 1}^{n-1} \sqrt{i} \leq \sum\limits_{i = 1}^{n-1} i = \binom{n}{2}$$$. SendThemToHell's expression $$$O(n\sqrt{n}) $$$ is a tighter upper-bound which is the discrete form of integrating $$$x^{0.5} dx$$$ as $$$x^{1.5}$$$. You can check the following Qura blog for more details What is the sum of the sequare roots of the first natural numbers

If all the $$$n-1$$$ non-root vertices are children of the root vertex, then the tree height is 2 and $$$\sum\limits_{i=1}^{n} \sqrt{size(i)} = \sqrt{n-1}$$$.

P.S.The aforementioned expressions do not include the vertex $$$v$$$ when computing $$$size(v)$$$.Mark all the vertices with size $$$\ge \sqrt{n}$$$. Among marked vertices there are no more than $$$\sqrt{n}$$$ vertices with at least two marked children, their total sum is bounded by $$$n$$$. For all marked vertices with no more than one marked child the sum of $$$size(v) - size(b(v))$$$ is bounded by $$$n$$$, because corresponding sets of vertices do not intersect. So, sum over all marked vertices is bounded by $$$2n$$$. Repeat the process on unmarked vertices inside their subtrees, the process will stop after $$$O(\log \log n)$$$ steps, so the sum is bounded by $$$O(n \log \log n)$$$.

Consider the heavy-light decomposition of the tree. Because $$$\sqrt{x+y} \leq \sqrt{x}+\sqrt{y}$$$, it's enough to bound the sum, over all nodes $$$u$$$ such that $$$u$$$ is a light child of its parent, of $$$\sqrt{size(u)}$$$. Split all such nodes into classes, the $$$k$$$-th class contains all nodes such that $$$2^k \leq size(u) < 2^{k+1}$$$. There are at most $$$n/2^k$$$ nodes in this class, and they together contribute at most $$$n/2^k*\sqrt{2^{k+1}}$$$ to the sum. Summing this over all values of $$$k$$$ and using the fact that a geometric series converges we obtain an upper bound of $$$O(n)$$$.

Hi :)

I have an O(n) algorithm:

You could define array h as follows:

h[v]=h[par[v]]+1;

h[root]=0;

the sum of all h[i] such that 0<=i<n and n (the number of the vertexes) is the answer.

here is the Code