Hi
We have a problem on a tree.
Imagine order of our algorithm is:
Sigma x(i) ^ 2
That if we define sz[v] as number of vertices in subtree of v, x(i) is number of different sz[u] between v's children.
It's easy to see it's O(n * sqrt(n)).
But after this submission for problem 1179D I saw it was realy fast and now I think it might be better than O(n * sqrt(n)).
Any idea?
Thanks from 300iq we got that it's O(n.lg(n)) and after that by dragonslayerintraining smart proof we got it's even O(n.lg(lg(n)).
But even after these proofs I wasn't done so after running the code on problem 1179D in gym and lots of random tests the largest
Sigma x(i) ^ 2
I could find was 1032859 for n <= 500,000 (about 2 * n or n.lg(lg(n)) / 2) so now I think O(n.lg(lg(n))) might be best
order we can proof for this algorithm, how ever some one might proof it's some thing better like O(n.log*), O(n) or...