It was based on DP on Tree. For each node, it was required to maintain the best values that can be obtained from rest of the nodes. Two DFS were required- one for calculating answers from descendants, and the other one from ancestors/siblings. Max of both the values will be the answer.

Was based on Mo's on Tree. In order to get the minimum absolute difference of squared values, there were 2 possible solutions. One can be to maintain 2 multisets. The first multiset stores the squared values of the nodes. The second multiset stores the difference between closest/adjacent values in the first multiset. Other was to use Segment Tree. At each node compute the minimum absolute difference of the squared value between its constituent leaf nodes.

The constraints indicate that the problem is to be solved using Matrix Exponentiation. However, the matrix used for matrix exponentiation will have dimensions of (N², N²), thereby leading to a complexity of O(N⁶Log(Y)). This will time-out. Proper observation will lead you to the fact that there is symmetry in the distribution of number of ways i.e we do not need N² points. Owing to symmetry, (N²) / 8 points are sufficient. This reduces the complexity by a great extent.

The answer is the summation of for all distinct values present in the list provided, where X is the frequency of the value.

The fact is that LCS and related stuff was of actually no importance. You can find the LCS anyhow using DP as the total length is just 5000. Based on the LCS values, you need to make an N * M matrix, which will be binary matrix. In this binary matrix, you need to find out how many squares of following form exist?

This square will have 1's on all of its borders as well as on the 45-degree diagonal. Other elements can be 0/1.
This can be solved using careful implementation of DP and then Merge Sort Tree or Square Root Decomposition.

We can maintain a sorted set of numbers by iterating over the array. We can simply use lower_bound in C++ or equivalent in other languages.
set<long long>::iterator it = s.lower_bound(val); it--; return (*it);