I think we don't actually use dp_ei, k, x ≤ dp_ei, k, y, x ≤ y. We can leave the residual in our current node for example. Then we use dp_ei, x, k ≤ dp_{ei, x + s, k + s}, x ≤ y, s is some non negative integer, which is true. I hope i didn't misunderstand something.

Indeed, the value does not increase monotonically with $$$a_i$$$. In my opinion, we could regard $$$a$$$ as a resource. When ensuring that the value is greater than $$$T$$$, we need to spend as little $$$a_i$$$ on the current edge as possible (make the $$$a-a_i$$$ as large as possible). In this way, there will be more ways to allocate the remaining edges (although this is a comment a long time ago, but I still reply here, hoping to help people who encounter this problem like me in the future)

I deem what STD wanted to tell us is that the answer k will not exceed 9 and we may maintain arrays of distinct substrings,or bitset as we merge the two demanded strings.But in fact the solutions you mentioned seem a little different from the original solution,because these solution get ans from three strings(itself,left and right strings) for each query.Hmm...I have read similar codes from submissions so I put forward my idea here~

The editorial assumes 10 is the answer and tries to see after all queries, if the number of unique substrings of length 10 can reach 2^10.

At first it explains how many substrings of length 10 there are in the original strings. Assume input is one long string of length 100, maximum number of unique substrings of length 10 won't be more than 100.

Now we need to know after each query, whats the maximum amount of new substrings of length 10 that can be added each time.

When we concatenate two strings, the new substrings of length 10 must start in the first string and end in the second. If it started and ended in the first string, that means its not newly created (same with the second). The maximum amount of new substrings of length 10 for each query therefore is 9.

So we started with 100 unique substrings of length ten, each query added 9.

Maximum amount when done is 100 + 9 *100 which is less than 2 ^10. So 10 cant be a possible answer.

In a good set, even problems of the form 0111 and 1000(for k=4) would work. Any pair of problems with bitwise AND=0 must work. I don't know why he wrote that.