Can you please explain your approach using suffix automat, heavy-light and convex hull? We tried something similar with suffix tree, centroid decomposition and FFT but didn't succeed.

Thanks in advance!

Problem D:

Firstly, we ignore some redundant strings, and we define $$$R(n)$$$ equals to the number of palindrome or concatenation of two palindromes. We can iterate the length of first palindrome (length maybe 0), and $$$R(n)=\sum_{i=0}^{n-1} k^{\lceil \frac{i}{2} \rceil} k^{\lceil \frac{n-i}{2} \rceil }$$$.

But some strings may be calculated multi times, like $$$abaaba$$$. We can assume that it is a palindrom or the concatenation of $$$aba$$$.

There is concolusion that a palindrome has two or more concatenation plans if and only if the palindrome $$$s$$$ has a period $$$p$$$ ($$$\forall i+p \lt |s|, s[i]=s[i+p]$$$) and $$$|s|$$$ can be divided by $$$p$$$. The number of plans is $$$|s|/p$$$ ($$$p$$$ is the period with minimum length of $$$s$$$).

So, we define $$$D(n)$$$ equals to the number of palindroms or strings that have only one kind of concatenation plan like $$$caba$$$. We need to substract the number of extra strings. With the concolusion above, we only need to iterate all the factors $$$l$$$ of $$$n$$$(except $$$n$$$ itself), and $$$D(n)=R(n)-\sum_{l|n \land l \lt n} \frac{n}{l} D(l)$$$.

Finally, the anser is $$$\sum_{i=1}^n \sum_{l|i} D(l)$$$. The time complexity is $$$O(n\sqrt{n})$$$ or $$$O(n\log n)$$$.

And it's essential to select initial integer x that gives maximum value like -11

The node you are looking for will be always on the center of the path between any team city and the fartest node from that team city. If that node doesn't satisfy the condition, then the answer is NO

Store the prefix sum array and binary search on the t_i values for each query. Store the result of every query. You can prove that this works in less than A_i * logN * log(A_i).