Hossam and (sub-)palindromic tree (Codeforces 1771D)
Tags: DP, trees

Hossam has an unweighted tree $$$G$$$ with letters in vertices.Hossam defines $$$s(v, \, u)$$$ as a string that is obtained by writing down all the letters on the unique simple path from the vertex $$$v$$$ to the vertex $$$u$$$ in the tree $$$G$$$.A string $$$a$$$ is a subsequence of a string $$$s$$$ if $$$a$$$ can be obtained from $$$s$$$ by deletion of several (possibly, zero) letters. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.A palindrome is a string that reads the same from left to right and from right to left. For example, "abacaba" is a palindrome, but "abac" is not.Hossam defines a sub-palindrome of a string $$$s$$$ as a subsequence of $$$s$$$, that is a palindrome. For example, "k", "abba" and "abhba" are sub-palindromes of the string "abhbka", but "abka" and "cat" are not.Hossam defines a maximal sub-palindrome of a string $$$s$$$ as a sub-palindrome of $$$s$$$, which has the maximal length among all sub-palindromes of $$$s$$$. For example, "abhbka" has only one maximal sub-palindrome — "abhba". But it may also be that the string has several maximum sub-palindromes: the string "abcd" has $$$4$$$ maximum sub-palindromes.Help Hossam find the length of the longest maximal sub-palindrome among all $$$s(v, \, u)$$$ in the tree $$$G$$$.Note that the sub-palindrome is a subsequence, not a substring.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 200$$$) — the number of test cases.The first line of each test case has one integer number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^3$$$) — the number of vertices in the graph.The second line contains a string $$$s$$$ of length $$$n$$$, the $$$i$$$-th symbol of which denotes the letter on the vertex $$$i$$$. It is guaranteed that all characters in this string are lowercase English letters.The next $$$n - 1$$$ lines describe the edges of the tree. Each edge is given by two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, \, u \le n$$$, $$$v \neq u$$$). These two numbers mean that there is an edge $$$(v, \, u)$$$ in the tree. It is guaranteed that the given edges form a tree.It is guaranteed that sum of all $$$n$$$ doesn't exceed $$$2 \cdot 10^3$$$.

Output: For each test case output one integer — the length of the longest maximal sub-palindrome among all $$$s(v, \, u)$$$.

Note: In the first example the maximal subpalindromes are "aaa" with letters in vertices $$$1, \, 3, \, 5$$$, or "aca" with letters in vertices $$$1, \, 4, \, 5$$$.  The tree from the first example. In the second example there is only one maximal palindrome "bacab" with letters in vertices $$$4, \, 2, \, 1, \, 5, \, 9$$$.  The tree from the second example. 

Sample Inputs:
2
5
abaca
1 2
1 3
3 4
4 5
9
caabadedb
1 2
2 3
2 4
1 5
5 6
5 7
5 8
8 9

Sample Outputs:
3
5

Solution (Python):
from collections import deque

def solve():
    n = int(input())
    s = input()
    adj = [[] for _ in range(n)]
    for __ in range(n - 1):
        (u, v) = readIntArr()
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
    dp = [[-1 for _ in range(n)] for __ in range(n)]
    q = deque()
    for u in range(n):
        q.append((u, u, -1, -1))
        dp[u][u] = 1
    while q:
        (u, v, u2, v2) = q.popleft()
        if u == v:
            for u3 in adj[u]:
                if dp[u3][v] == -1:
                    if s[u3] == s[v]:
                        dp[u3][v] = dp[v][u3] = 2
                    else:
                        dp[u3][v] = dp[v][u3] = 1
                    q.append((u3, v, u, -1))
        else:
            for u3 in adj[u]:
                (uu, vv, uprev, vprev, uprevprev) = (u3, v, u, v2, u2)
                if uu != uprevprev and dp[uu][vv] == -1:
                    dp[uu][vv] = dp[uprev][vv]
                    if vprev == -1:
                        vprev = uprev
                    dp[uu][vv] = max(dp[uu][vv], dp[uu][vprev])
                    if s[uu] == s[vv]:
                        dp[uu][vv] = max(dp[uu][vv], dp[uprev][vprev] + 2)
                    q.append((uu, vv, uprev, vprev))
                    dp[vv][uu] = dp[uu][vv]
            for v3 in adj[v]:
                (uu, vv, uprev, vprev, vprevprev) = (u, v3, u2, v, v2)
                if vv != vprevprev and dp[uu][vv] == -1:
                    dp[uu][vv] = dp[uu][vprev]
                    if uprev == -1:
                        uprev = vprev
                    dp[uu][vv] = max(dp[uu][vv], dp[uprev][vv])
                    if s[uu] == s[vv]:
                        dp[uu][vv] = max(dp[uu][vv], dp[uprev][vprev] + 2)
                    q.append((uu, vv, uprev, vprev))
                    dp[vv][uu] = dp[uu][vv]
    ans = 0
    for u in range(n):
        for v in range(n):
            ans = max(ans, dp[u][v])
    return ans

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        ans = solve()
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (n + 1) + v

def make_graph(n, m):
    (x, s) = ([], [0] * (n + 3))
    for _ in range(m):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        x.append(u)
        x.append(v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    s = [0] + list(input().rstrip())
    (G, s0) = make_graph(n, n - 1)
    m = (n + 1) * (n + 1)
    dp = [-2] * m
    for i in range(n + 2, m, n + 2):
        dp[i] = 1
    (q, k) = ([], 0)
    for i in range(1, n + 1):
        for u in range(s0[i], s0[i + 1]):
            j = G[u]
            x = f(i, j)
            dp[x] = 1 if s[i] ^ s[j] else 2
            if i < j:
                q.append(x)
    while len(q) ^ k:
        qk = q[k]
        (i, j) = divmod(qk, n + 1)
        for u in range(s0[i], s0[i + 1]):
            l = G[u]
            x = f(l, j)
            if dp[x] >= 0:
                i0 = l
            elif dp[x] == -2:
                (dp[x], dp[f(j, l)]) = (-1, -1)
                q.append(x)
        for u in range(s0[j], s0[j + 1]):
            l = G[u]
            x = f(i, l)
            if dp[x] >= 0:
                j0 = l
            elif dp[x] == -2:
                (dp[x], dp[f(l, i)]) = (-1, -1)
                q.append(x)
        if k < n - 1:
            k += 1
            continue
        if s[i] ^ s[j]:
            dp[qk] = max(dp[f(i, j0)], dp[f(i0, j)])
        else:
            dp[qk] = max(dp[f(i, j0)], dp[f(i0, j)], dp[f(i0, j0)] + 2)
        dp[f(j, i)] = dp[qk]
        k += 1
    ans0 = max(dp)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from collections import deque

def createGraph(n, m):
    deg = [0] * (n + 2)
    edges = [0] * (2 * m)
    for i in range(m):
        (u, v) = map(int, input().split())
        deg[u + 1] += 1
        deg[v + 1] += 1
        edges[2 * i] = u
        edges[2 * i + 1] = v
    for i in range(3, n + 2):
        deg[i] += deg[i - 1]
    adj = [0] * (2 * m)
    for i in range(2 * m):
        u = edges[i]
        adj[deg[u]] = edges[i ^ 1]
        deg[u] += 1
    return (adj, deg)
T = int(input())
ans = [0] * T
for t in range(T):
    n = int(input())
    s = ' ' + input()
    if n == 1:
        ans[t] = 1
    else:
        (adj, deg) = createGraph(n, n - 1)
        dp = [0] * ((n + 1) * (n + 1))
        for i in range(n + 1):
            dp[i * n + i] = 1
        pairs = deque()
        dist1 = 0
        for v in range(1, n + 1):
            for i in range(deg[v - 1], deg[v]):
                u = adj[i]
                if u > v:
                    if s[v] == s[u]:
                        dp[v * n + u] = dp[u * n + v] = 2
                    else:
                        dp[v * n + u] = dp[u * n + v] = 1
                    pairs.append((u, v))
                    dist1 += 1
        while pairs:
            (u, v) = pairs.popleft()
            for i in range(deg[v - 1], deg[v]):
                w = adj[i]
                if dp[w * n + u] == 0:
                    if w > u:
                        pairs.append((w, u))
                else:
                    v0 = w
            for i in range(deg[u - 1], deg[u]):
                w = adj[i]
                if dp[w * n + v] == 0:
                    if w > v:
                        pairs.append((w, v))
                else:
                    u0 = w
            if dist1 > 0:
                dist1 -= 1
            else:
                dp[u * n + v] = dp[v * n + u] = max(dp[u0 * n + v], dp[v0 * n + u], dp[v0 * n + u0] + 2 * int(s[u] == s[v]))
        ans[t] = max(dp)
print('\n'.join(map(str, ans)))