In the last round (round 1048), I solved the (2138C2) Maple and Tree Beauty (Hard Version) using divide and conquer method and NTT. The problem could be solved by doing binary search on the length of the LCS. For that I can precalculate the number of nodes at every depth, afterwards assign all nodes of a certain depth either white or black color. I can check whether it’s possible by calculating all possible subset sums using NTT and divide and conquer. But every search I would have to calculate NTT using divide and conquer technique which would get me TLE.

To bypass this repeated calculation I tried a modified method of DnC. At first I calculated the NTT for the left subrange for divide and conquer. Afterwards I checked if I only considered the left subrange and could get a common prefix string of that range for the tree. If I could, then I moved to the right subrange, otherwise move to the left subrange. And afterwards repeatedly execute this process by dividing that subrange into left and right. This made sure that I am calculating divide and conquer NTT for the at most twice for each subrange of DnC. However, that also meant that the other half wouldn't be traversed. Making it equivalent to calculating the answer for the whole tree just once.

This was definitely a overkill and not the intended solution, but I knew it could be solved with DnC NTT so I just did. It was fun doing so. Did anyone else try the same idea?