I recently came across a claim about binary trees that I was unable to prove. Given a binary tree, $$$\sum{|child_l|\times |child_r| } = O(N^2)$$$
Could someone provide proof and/or a way to intuitively explain this?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
I recently came across a claim about binary trees that I was unable to prove. Given a binary tree, $$$\sum{|child_l|\times |child_r| } = O(N^2)$$$
Could someone provide proof and/or a way to intuitively explain this?
Name |
---|
Actually, I guess I have some kind of intuitive explanation behind this. If we imagine that each node "contributes" to the $$$N^2$$$ count, we can observe that no matter how the tree is structured, the total number that it contributes will be maximum $$$N$$$, since once two subtrees "merge" they will no longer multiply within themselves to count towards the $$$N^2$$$. So, since each node will add a maximum of $$$N$$$ towards the count, the total number will add up to maximum $$$N^2$$$. I think I am more interested in formal proof.
Another way to think about it is that any pair of nodes $$$(u, v)$$$ is considered at most (exactly, in fact) once and this happens at their LCA.
Not every pair will be there. $$$(u,v)$$$ where v is an ancestor of u wont be present in the enumeration
I think this also proves the time complexity of Combining Subtrees DP
Suppose we want to count number of pairs $$$(u, v)$$$ such that $$$LCA(u, v) = i$$$. If children of $$$i$$$ are $$$l$$$ and $$$r$$$, then the number is equal of $$$\text{SubtreeSize}(l) \times \text{SubtreeSize}(r)$$$ if we consider pairs $$$(u, v)$$$ and $$$(v, u)$$$ equal. Therefore the sum you mentioned is equal to total number of pairs of vertices in the tree (number of subsets of size two).
Total number of pairs except the ones $$$\{u,v\}$$$ where $$$u$$$ is an ancestor of $$$v$$$ since $$$LCA(u,v) = u$$$ but this is not counted in $$$\text{SubtreeSize} (l_u) \times \text{SubtreeSize} (r_u)$$$
The given sum is same as the union of cross products of sets of vertoces of left and right subtrees. Now we can see that each unordered pair of vertices $$$(u,v)$$$ occurs atmost once in the above union. This also gives an upper bound of $$$N*(N-1)/2$$$
https://codeforces.me/blog/entry/124538?#comment-1105664