P9664 [ICPC 2021 Macao R] LCS Spanning Tree

给定一个有 $n$ 个顶点的完全无向图和 $n$ 个字符串 $s_1, s_2, \cdots, s_n$，连接顶点 $i$ 和 $j$ 的边的权重等于字符串 $s_i$ 和 $s_j$ 的最长公共子串（LCS）的长度。计算此图上任意生成树的最大总权重。 一个字符串的子串可以通过从该字符串的开头和/或结尾删除一些（可能为零）字符来获得。例如，“maca”、“aca” 和“cau”都是“macau”的子串，而“acu”不是。

无

无