PouyaNavid's blog

By PouyaNavid, history, 15 months ago,

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))}$ ?

• +48

 » 15 months ago, # | ← Rev. 3 →   +108 $O(n\sqrt{n})$ ofc, consider a bamboo, $\sum\limits_{i = 1}^{n}{\sqrt{i}} \ge \frac{n}{2}\sqrt{\frac{n}{2}}$
 » 15 months ago, # | ← Rev. 8 →   0 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)$.
 » 15 months ago, # |   +73 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)$.
 » 15 months ago, # |   +171 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)$.
 » 15 months ago, # |   -100 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 #define pb push_back using namespace std; const int maxn=1e5+10; int n,root; vectoradj[maxn]; bool mark[maxn]; int h[maxn]; void dfs(int v) { mark[v]=1; for(int i=0;i>n>>root; for(int i=0;i>u>>v; adj[u].pb(v); adj[v].pb(u); } dfs(root); int Sum=0; for(int i=0;i