相当抽象的一道题，看了好几遍题解才看明白的
题目大意：
给定字符串 \(S_0\)（即绫的法术源），要求进行一下操作：
-
光归：对于\(T\)（\(T\) 为 \(S\) 的最大回文后缀），使 \(S \leftarrow T\)，消耗 \(A\) 时间
-
光辉： 对于\(T\)（\(T\) 为 \(S\) 的最大回文后缀且\(T\) 为 \(S\) 的子串），使 \(S \leftarrow T\)，消耗 \(B\) 时间
-
光隐： 对于\(T\)（\(T\) 为把 \(S\) 删去其长度相等且长度不大于 \(k\) 的前缀与后缀），\(S \leftarrow T\)，消耗 \(C\) 时间
-
光腾：对于\(T\)（\(T\)为在 \(S\) 两边分别加入 \(P\) 和 \(Q\) ），\(S \leftarrow T\)，消耗 \(D\) 时间
-
光戈：对于\(T（T = a + S ）\)，\(S \leftarrow T\)，在使用此变换之后，无法再使用其它类型的法术变换 ，消耗 \(E\) 时间
求阿绫最少需要多少次才能使 \(S=T\)
万物有灵，法术亦是如此。
思路：
什么破题什么破题什么破题什么破题什么破题什么破题
这题要当图论打
- 光归：直接连 \((i,fail_i,A)\)
void sky_regression(){//光归
for(long long i=2;i<=cnt;i++){
add(i,t[i].fail,A);
}
}
- 光辉：连 \((i,fail_iB)\)
void sky_shine(){//光辉
for(long long i=2;i<=cnt;i++){
add(t[i].fail,i,B);
}
}
- 光隐：处理一下\(i\)，连 \(k\) 条\((i,fa_i,C)\)
void sky_stealth(){//光隐
for(long long i=2;i<=cnt;i++){
long long x=t[i].fa;
for(long long j=1;x && j<=k;x=t[x].fa,j++){
add(i,x,C);
}
}
}
-
光腾：把 \(i\) 向 \(i\) 的子树中任一节点转移，代价为 \(D\)
然后看了题解发现复杂度大到飞起，只好建立虚树（但是我没学）
于是我就看了2个小时的OI-wiki差不多懂了但好像没那么懂
每个点建立虚点，能且只能以\(0\)的代价向子的节点转移
连\((i^‘,i,0)\)和\((i,i^`,D)\)即可
void sky_feiteng(){//光腾
for(long long i=2;i<=cnt;i++){
add(i+cnt,i,0);
}
for(long long i=2;i<=cnt;i++){
add(i,i+cnt,D);
}
for(long long i=2;i<=cnt;i++){
if(t[i].fa>1){
add(t[i].fa+cnt,i+cnt,0);
}
}
}
- 光戈：由于使用后不能使用其他操作，所以单独分开
接下来建回文自动机，因为我不会所以去抄了一个，这题就当练图论了
然后跑一遍堆优化dij结合DP转移就行