Moje rozwiązanie jest w O(n^2) (średnio), ale tylko 6/10, trochę za wolne.

Zaczynam od najwyższych podatków. Jak już ustalę ile jakich chcę zapłacić wysokich podatków dla każdego poziomu, to te wysokie podatki reprezentuję przez losowe liczby modulo liczba pierwsza, i szukam takich ścieżek żeby suma się zgadzała modulo p.

Też tak robię. Jak zliczasz ścieżki o danej sumie w O(n)? Ja mam to w O(n log n) (i dostałem 4/10).

Dla każdej krawędzi z daną wysokością podatku szukam ścieżek, dla których ta krawędź jest pierwszą krawędzią o tym podatku.

Więc po jednej stronie tej krawędzi patrzę na wszystkie wierzchołki do których można dojść bez przechodzenia przez inne krawędzie o tym samym podatku, i dodaję je do tablicy haszującej gdzie kluczem jest suma wyższych podatków (reprezentowanych przez losowe liczby), a wartością jest liczba wierzchołków.

Po drugiej stronie danej krawędzi przechodzę przez całe drzewo po tej stronie i dla każdego wierzchołka po tej stronie liczę ile brakuje wyższych podatków, i patrzę w tablicy haszującej ile jest pasujących wierzchołków po drugiej stronie.

My solution is O(n log^3 n) and got 10.

Using binary search, we need to count the number of paths whose sum is no more than something, which can be done using centroid decomposition and two-pointers.

To handle the huge number, we can use persistent segment tree storing hash on each node to compare two huge numbers in O(log n) time.

I had a similar idea, that I am now trying to finish debugging, but in O(n log^4 n) because don't you need to use something like an order statistic tree to count the number of paths whose sum is more than something?

And how do you find the "something" to do the binary search? Do you take it to be the length of a random path in the search interval, like I am going to?

Also, I am going to use small-to-large instead of centroid decomposition but this doesn't change the complexity.

Yeah, no need to use something like an order statistic tree to count the number of paths whose sum is more than something.

We can do the centroid decomposition at first, and sort these O(n log n) values in advance before the binary search, thus we can just use two-pointers in each check.

To find something to do the binary search, we can note that the answer is always "pool[i]+pool[j]"(1<=i<=j<=cnt), where cnt=O(n log n). Assume we now have "answer in (l,r)", we can do a two-pointers to find the number of pairs (i,j) such that l<pool[i]+pool[j]<r. If this number is not large, for example not more than 2e5, we can generate these pairs, sort them, and then run a binary search on them. Otherwise, we can just select a random pair, it won't increase the times of check too much.

Oh, all right. Thank you. In this case I actually don't know how to translate it to a solution using small-to-large instead of centroid decomposition.

I suppose you need to be careful when the answer is among more than 2e5 of the same distances just like we have to be careful when we want write the Selection Rank Algorithm when the elements are not unique (then we need to partition the set inside which we search into three chunks: less than pivot, equal to pivot, and greater than pivot). I wonder if there was such a test. This is also a thing I would need to fix in what I wrote.

And when you have not more than 2e5 candidates for the answer and you generate them, I suppose you could run a linear Selection Rank Algorithm to find the answer. And if you sort all these candidates, then you can just pick the element with the required rank from them in constant time, you don't need to a binary search, do you?

pool is just a list, pool[i]+pool[j] is not always a valid path because i and j may come from the same subtree of the centroid. So I must do binary search even when there is no more than 2e5 candidates.