$$$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:

1. 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

2. 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

Your code here...
#include<bits/stdc++.h>
#define  pb push_back
using namespace std;
const int maxn=1e5+10;
int n,root;
vector<int>adj[maxn];
bool mark[maxn];
int h[maxn];
void dfs(int v)
{
    mark[v]=1;
    for(int i=0;i<adj[v].size();i++)
    {
        int u=adj[v][i];
        if(!mark[u])
        {
            h[u]=h[v]+1;
            dfs(u);
        }
    }
}
int main()
{
    cin>>n>>root;
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(root);
    int Sum=0;
    for(int i=0;i<n;i++)
    {
        Sum+=h[i]+1;
    }
    cout<<Sum;
}