Subtree size. if we take 'i' as a root, size[i] represents the numbers of nodes in his tree. Simply size array represents subtree size.

Is it possible to extend the start time of 30 minutes? Cause In Bangladesh, India region it's Iftar time.

add: minus contribution for asking a question! RIP people :) As a contestant, I don't want to miss any contest.

its nlogn,

ok lets take an example,,

suppose the tree is,

In this tree centroid is 2.. ->now we traverse whole tree for a specific answer,

->then delete 2 from tree.

-> now we got three subtree ,

now, if we take subtree which contain 1,3,6,7 node.. and we go through this process , we got 3 as a centroid.

now again we got three subtree 1 , 6 , 7. and we delete 3 from the tree.

so its clear every time we divide a tree = how many adjacent node a centroid have.. they must be smaller than sz/2 . so its easy to check the complexity.

if we thought about binary tree, ( cause binary tree creates highest compexity here and you can understand easily)

from 1 centroid we delete one node get two subtrees (2 centroid) ,, take complexity O(n)

from 2 centroid we delete two nodes get 4 subtrees ( 4 centroid) ,, take compexity O(n-1)

from 4 centroid we delete 4 nodes, get 8 subtrees (8 centroid) ,, take complexity O(n-3) // 3 nodes already deleted before this process start

from 8 -----> 16 subtrees----> 16 centroid----> complexity O(n-7) // 7 nodes deleted

so if we sum all we get = O(n) + O(n-1) + O(n-3) + O(n-7) + O(n-15)+....... == nlogn

if this is not a binary tree, this complexity will be less than nlogn..

I think you can understand it.

thank you

Yes. Cause every node visited at most logn time..

So for n node.. it takes nlogn :)

we like codeforces for so many reasons, but two reasons effected me well.

1. Different types of solution from great people. Also so many different types of problem. I think this increases our think ability.
2. Blog system. Last two years we don't get enough resources, but in 2019.. so many interesting blog was made by best programmer. It helps us a lot. They just share their knowledge as much as possible . Thank you brothers <3 .

we want to thank you codeforces and their amazing system.

Thank you. Edited

No. just for fun. Nothing else

Thank you. But we need to choose one. And two node must have same subtree size. edited

i only know fast walsh hadamard gives us... all pairs xor/and/or sum. i don't know about this variation. Thanks.

is it possible in fft.. all possible x^y minimum value...

like , A = a1x^3 + b1x^2+ c1x + d1 B = a2x^3 + b2x^2+ c2x + d1 now possible possible way to create x^3= (a1*d1),(b1*c2),(c1*b2),(d1*a2) now i want min((a1*d1),(b1*c2),(c1*b2),(d1*a2))

if any other algorithm what is it?

Auto comment: topic has been updated by YoyOyoYOy000y000 (previous revision, new revision, compare).

In this problem, i saw that everyone use higher prime. In lower prime they get Wa.. They use 10^10 up primes.

thanks vai..i think for these problem we need higher prime, cause nodes can be up to 10^5 ..i am not sure.

if same ques with 9..then can we use 2nd approch?

thanks i got it...yeah there have some mistake.. for large number it's quite impossible there is no exact solution for this ques with 9 sec :) thank you :)