rt.

本题在图上做区间 dp，状态设计和转移十分巧妙，同时输出回文串部分较为复杂，所以建议评紫。