题解：P8406 [COCI 2021/2022 #6] Palindromi

· · 题解

提供简短一点的代码。

其实就是回文树的启发式合并模板题目，时间复杂度为 \mathcal{O}(n\log n)。

那么我们需要实现回文树的向前插入。

考虑向前插入需要新考虑啥。

对于 ch_{u,c}，显然向前向后都一样的使用。

对于 fail_u，表示当前节点的最长回文后缀，但我们现在想要知道最长回文前缀。

不过由于节点 u 代表的也是一个回文串，那么这两个其实就是一个东西。

那么向前插入本质上和向后插入差不多，唯一需要注意的就是你的代码实现中向前插入时，下标要特殊处理一下，以及此时需要维护前缀最大回文和后缀最大回文的两个节点下标。

且若现在整个串都为回文串，那么会对两个下标都造成影响。

代码中下标从 0 开始，细节有点多。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=1e5+5,M=N*19,INF=0x3f3f3f3f;
struct pam{
    #define w(x) (op?sz-(x):(x))
    struct node{int ch[2],len,fail;}tmp;
    vector<node> a;int laspre,lassuf,ans;
    deque<int> s;
    int New(int len,int fail){tmp.len=len,tmp.fail=fail;a.p_b(tmp);return a.size()-1;}
    pam(){New(0,1);New(-1,1);laspre=lassuf=1;}
    void insert(int c,int op){
        if(!op)s.p_b(c);
        else s.push_front(c);
        int i=s.size()-1,sz=s.size()-1;
        int &las=op?laspre:lassuf;
        while(i-a[las].len-1<0||s[w(i)]!=s[w(i-a[las].len-1)])las=a[las].fail;
        if(a[las].ch[c]) las=a[las].ch[c];
        else{
            int tp=a[las].fail;
            while(i-a[tp].len-1<0||s[w(i)]!=s[w(i-a[tp].len-1)]) tp=a[tp].fail;
            int u=New(2+a[las].len,a[tp].ch[c]);
            a[las].ch[c]=u;las=u;ans++;
            if(a[las].len==s.size())laspre=lassuf=u;
        }
    }
}T[N];
int fa[N],n;
int find(int u){
    if(fa[u]==u) return u;
    return fa[u]=find(fa[u]);
}
int main(){
    n=rd();
    for(int i=1;i<=n;i++){
        char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();
        T[i].insert(ch-'0',0);fa[i]=i;
    }
    for(int i=1;i<n;i++){
        int u=rd(),v=rd();
        u=find(u),v=find(v);
        if(T[v].s.size()<=T[u].s.size()){
            int sz=T[v].s.size();
            for(int i=0;i<sz;i++) T[u].insert(T[v].s[i],0);
            fa[v]=u;printf("%d\n",T[u].ans);
        }
        else{
            int sz=T[u].s.size();
            for(int i=sz-1;i>=0;i--) T[v].insert(T[u].s[i],1);
            fa[u]=v;printf("%d\n",T[v].ans);
        }
    }
    return 0;
}