Subtask 1

Với mỗi cặp đỉnh ~(u, v)~, ta có thể tính ~dp_{u, v}~ trong ~O(n^2)~.

ĐPT ~O(n^4)~.

Subtask 2

Gọi ~dp_{u,v}~ là độ dài dài nhất của các ~sub-palindrome~ của chuỗi đạt được từ các ký tự trên đường đi từ ~u~ tới ~v~. Giả sử ~v~ là con của ~u~, ~x~ là con trực tiếp của ~u~ và ~y~ là cha trực tiếp của ~v~. Khi đó ta có công thức sau:

• ~dp_{u,v} = dp_{x, y} + 2~ nếu ~s_u = s_v~.
• ~dp_{u,v} = max(dp_{x, v}~, ~dp_{u, y})~ nếu ngược lại.

ĐPT ~O(n^2)~.

Subtask 3

Giả sử ~v~ là đỉnh có độ sâu hơn ~u~.

Nếu ~u = v~: ~dp_{u, v} = 1~.

Nếu ~u~ là cha trực tiếp của ~v~:

• ~dp_{u,v} = 1~ nếu ~s_u = s_v~.
• ~dp_{u,v} = 2~ nếu ngược lại.

Nếu ~u~ là cha không trực tiếp của ~v~. Gọi ~x~ là con trực tiếp của ~u~, ~y~ là cha trực tiếp của ~v~:

• ~dp_{u,v} = dp_{x, y} + 2~ nếu ~s_u = s_v~.
• ~dp_{u,v} = max(dp_{x, v}, dp_{u, y})~ nếu ngược lại.

Nếu ~u~ không là cha của ~v~. Gọi ~x~, ~y~ lần lượt là cha trực tiếp của ~u~ và ~y~:

• ~dp_{u,v} = dp_{x,y} + 2~ nếu ~s_u = s_v~.
• ~dp_{u,v} = max(dp_{x, v}, dp_{u, y})~ nếu ngược lại.

ĐPT ~O(n^2)~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 2;

int n, dp[N][N], P[N];
string s;
vector<int> adj[N];

void calcDP1(int u, int p) {
    P[u] = p;
    for(int p = P[u], last_p = u; p != 0; last_p = p, p = P[p]) {
        dp[p][u] = 0;
        if (s[p] == s[u]) dp[p][u] = max(dp[last_p][P[u]], 0) + 2;
        dp[p][u] = max({dp[p][u], dp[last_p][u], dp[p][P[u]]});
        dp[u][p] = dp[p][u];
    }
    for(int& v : adj[u]) if (v != p) {
        calcDP1(v, u);
    }
}
int DP(int u, int v) {
    int& res = dp[u][v];
    if (~res) return res;
    if (s[u] == s[v]) res = DP(P[u], P[v]) + 2;
    res = max({res, DP(P[u], v), DP(u, P[v])});
    return dp[v][u] = res;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(dp, -1, sizeof dp);
    for(int i = 1; i <= n; ++i) dp[i][i] = 1;
    calcDP1(1, 0);
    int res = 0;
    for(int i = 1; i <= n; ++i) for(int j = i; j <= n; ++j) res = max(res, DP(i, j));
    cout << res;

    return 0;
}