この問題の解法として、以下のようなものが挙げられます。

• \(A_{i,j} = 1\) を満たす \((i,j)\) に対して、\(T\) における \(i\) から \(j\) への単純パスが通る頂点を \(v_1=i,v_2,\dots,v_n=j\) としたとき \(x_{v_k} = x_{v_{n-k+1}}\) という条件をつける。
• unionfind 等を用いて、上記の \(x_i = x_j\) が等しいという条件を全て満たす \(x\) を一つ構築する。ただし、等しくなくてもよい要素同士が等しくなってはならない。
• \(x\) のスコアを実際に計算する。

ですが、愚直に上記を行ってしまうと \(\mathrm{O}(N^3)\) かかってしまいます。これを高速化しましょう。

上記の解法の無駄な部分として、同じ \(i,j\) について \(x_i = x_j\) という条件を複数個作っていることが挙げられます。これを改善するために、以下の事実を利用します。ただし、\(f(i,j)\) で \(i\) から \(j\) への単純パス上の点のうち、\(i\) に隣接している頂点番号を表します。これは各点から dfs をすることで \(\mathrm{O}(N^2)\) で前計算できます。

• \((i,j)\) が回文ペアであることと、\((f(i,j),f(j,i))\) が回文ペアかつ \(x_i = x_j\) であることは同値である。

これを利用するために、\(d = N-1,N-2,\dots,2\) の順に以下を行えばよいです。

• 距離が \(d\) である頂点の組 \((i,j)\) 全てに対して、\(A_{i,j} = 1\) ならば、\(A_{f(i,j),f(j,i)} = 1\) にして、\(x_i = x_j\) という制約をつける。

すると、\(\mathrm{O}(N^2)\) で \(x_i = x_j\) という条件を全て列挙できます。これを用いて \(x\) を \(1\) 個構築するのは \(\mathrm{O}(N^2)\) で可能です。

\(x\) のスコアを計算しましょう。これは、上記を逆順に行えばよいです。つまり、\(d = 2,3,\dots,N\) の順に以下を行えばよいです。

• 距離が \(d\) である頂点の組 \((i,j)\) 全てに対して、\((f(i,j),f(j,i))\) が回文ペアかつ \(x_i = x_j\) ならば、\((i,j)\) を回文ペアと判定する。

これで \(\mathrm{O}(N^2)\) でスコアを計算できます。よって、上記の方法によりこの問題を \(\mathrm{O}(N^2)\) で解くことが出来ます。