A solution proceeds as follows.

• For every pair \((i,j)\) with \(A_{i,j}=1\), let the simple path in \(T\) be \(v_1=i,v_2,\dots,v_n=j\) and impose the requirement \(x_{v_k}=x_{v_{n-k+1}}\).
• Using a union-find (or similar), construct a sequence \(x\) that satisfies all requirements \(x_i = x_j\) above. Here, elements that are not required to be equal must not be equal.
• Compute the score of \(x\).

A naive implementation of this takes \(\mathrm{O}(NM)\) time; we speed it up.

The slow part of the above solution is where it imposes the condition \(x_i = x_j\) for the same \(i,j\) multiple times. To improve this, we use the following fact. Here, \(f(i,j)\) denotes the index of the vertex adjacent to \(i\) on the path from \(i\) to \(j\). It can be precomputed in \(\mathrm{O}(N^2)\) time by running DFS from every vertex.

• \((i,j)\) is a palindromic pair if and only if \((f(i,j),f(j,i))\) is a palindromic pair and \(x_i=x_j\).

To use this fact, for \(d = N-1,N-2,\dots,2\) in this order, do the following:

• For every pair of vertices \((i,j)\) at distance \(d\), if \(A_{i,j}=1\), then set \(A_{f(i,j),f(j,i)}=1\) and add the requirement \(x_i = x_j\).

This enumerates all requirements in \(\mathrm{O}(N^2)\) time. They can be used to construct one \(x\) in \(\mathrm{O}(N^2)\) time.

To compute the score of \(x\), run the above procedure in reverse order. That is, for \(d=2,3,\dots,N\) in this order, do the following:

• For every pair of vertices \((i,j)\) at distance \(d\), if \((f(i,j),f(j,i))\) is a palindromic pair and \(x_i=x_j\), then declare \((i,j)\) a palindromic pair.

This computes the score in \(\mathrm{O}(N^2)\) time. Hence, this method solves the problem in \(\mathrm{O}(N^2)\) time.