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 O(n).