P5841 题解

· · 题解

题目传送门

P5841

分析

先把所有字符串建到一颗 Trie 树上。

第一问

要求 W(P) 尽量地大，就是要求字符串在 Trie 树上的 LCA 的深度尽量地大。

引理：在一颗有 n 个节点的有根树上，设树的节点标号为一种 dfs 序，对于 i \in [1,n] 满足：

dep_{\operatorname{lca}(1,i)} \le dep_{\operatorname{lca}(2,i)} \le \dots \le dep_{\operatorname{lca}(i-1,i)} \le dep_{\operatorname{lca}(i,i)} \ge dep_{\operatorname{lca}(i,i+1)} \ge \dots \ge dep_{\operatorname{lca}(i,n)}

可以理解为：

和一个节点在一个方向上 dfs 虚越接近的节点，它们的 lca 的深度越大。

所以我们必然是按照字典树上的 dfs 序进行排列的。

我们在每一个字符串的末尾加一个特殊字符来避免前缀关系，便于处理。

所以，设虚根的深度为 0，第一问的答案就是 \sum_{i=1}^{cnt} \max(0,child_{i}-1) \times dep_i^2，其中 cnt 是 Trie 树上的节点数量。

第二问和第三问

由于第 i 个附加任务的贡献是 2^i，所以一个附加任务的贡献必然大于它前面的所有附加任务的贡献和，我们必然是从后到前尝试满足这些附加任务。

我们对于 Trie 树上每一个节点的儿子们建若干个链表。

我们要求节点 u 在节点 v 的前面，先求出 \operatorname{lca}(u,v)，记为 x，则 u 到 u 深度高于 x 的祖先必然是其子树中最后一个被遍历的，v 到 v 深度高于 x 的祖先必然是其子树第一个被遍历的，而 u 这棵子树的遍历顺序一定恰好在 v 这棵子树的后面一位。

于是我们写了一些函数：

inline bool check_first(int u,int x)
{
    while(f[u] != x)
    {
        if(fir[f[u]]&&fir[f[u]] != u) return 0;
        if(pre[u]) return 0;
        if(tail[u]&&tail[u] == las[f[u]]&&len[u] != child[f[u]]) return 0;
        u = f[u];
    }
    return 1;
}
inline bool check_last(int u,int x)
{
    while(f[u] != x)
    {
        if(las[f[u]]&&las[f[u]] != u) return 0;
        if(nxt[u]) return 0;
        if(head[u]&&head[u] == fir[f[u]]&&len[head[u]] != child[f[u]]) return 0;
        u = f[u];
    }
    return 1;
}
inline bool check(int u,int v,int x)
{
    while(f[u] != x) u = f[u];
    while(f[v] != x) v = f[v];
    if(nxt[u] == v&&pre[v] == u) return 1;
    if((nxt[u]&&nxt[u] != v)||(pre[v]&&pre[v] != u)) return 0;
    if(head[u] == v&&tail[v] == u) return 0;
    if(fir[x]&&las[x]&&head[u] == fir[x]&&tail[v] == las[x]&&len[head[u]] + len[v] != child[x]) return 0;
    if(u == las[x]||v == fir[x]) return 0;
    return 1;
}

我们要判断的有三点：

如果满足，就把 u 到 u 深度高于 x 的祖先设置为其子树中最后一个被遍历的，v 到 v 深度高于 x 的祖先设置为其子树第一个被遍历的，把 u 和 v 接起来，并标记可以满足。

if(check_last(u,x)&&check_first(v,x)&&check(u,v,x))
{   
    while(f[u] != x)
    {
        las[f[u]] = u;
        u = f[u];
    }
    while(f[v] != x)
    {
        fir[f[v]] = v;
        v = f[v];
    }
    if(pre[v] != u||nxt[u] != v)
    {
        pre[v] = u;
        nxt[u] = v;
        head[tail[v]] = head[u];
        tail[head[u]] = tail[v];
        len[head[u]] += len[v];
        len[v] = 0;
        head[u] = tail[v] = 0;  
    }
    ++ans;
    mark[i] = 1; 
}

这个链表的判断和操作较为复杂，写之前建议自己在草稿纸分析一下情况。

最后，再按照链表确定的 dfs 序输出答案。

此时的时间复杂度是：O(q\sum|S|)。

优化

可以发现，在考虑 dfs 序时，一些很长的链是无用的，考虑压缩。

对于仅有一个儿子的节点，可以省略它。

int build(int u)
{
    if(!child[u]) return u;
    F(i,0,26)
        if(son[u][i]) 
        {
            int v = build(son[u][i]);
            if(child[u] == 1) return v;
            g[u].push_back(v); 
            f[v] = u;
        }
    return u;
}
rt = build(1);

此时，Trie 树的最大深度约为 \sqrt{\sum{|S|}}。

故时间复杂度为 O(q\sqrt{\sum{|S|}})。

就可以通过此题了！

代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
    register T p = 1;
    x = 0;
    char c = getchar();
    while(c < '0'||c > '9')
    {
        if(c == '-') p = -p;
        c = getchar();
    }
    while('0' <= c&&c <= '9')
    {
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    x *= p;
}
template<typename T>inline void write(register T x)
{
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) write(x/10);
    putchar(x%10+48);
}
#define D(i,a,b) for(register int i=a;i>=b;--i)
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define ull unsigned long long
#define ll long long
#define pii pair<int,int> 
#define N 200010
bitset<N> mark;
vector<int> g[N];
ll sum = 0;
pii p[N];
int son[N][30],f[N],child[N],ed[N],id[N],dep[N];
int head[N],tail[N],nxt[N],pre[N],len[N],fir[N],las[N];
int n,m,cnt = 1,rt = 0,ans = 0;
string s;
int build(int u)
{
    if(!child[u]) return u;
    F(i,0,26)
        if(son[u][i]) 
        {
            int v = build(son[u][i]);
            if(child[u] == 1) return v;
            g[u].push_back(v); 
            f[v] = u;
        }
    return u;
}
inline int lca(int u,int v)
{
    if(dep[u] < dep[v]) swap(u,v);
    while(dep[u] > dep[v]) u = f[u];
    while(u != v) u = f[u],v = f[v];
    return u;
}
void dfs(int u)
{
    if(!child[u]) 
    {
        write(ed[u]);
        putchar(' ');
        return;
    }
    vector<int> e[3];
    for(auto v:g[u])
    {
        if(pre[v]) continue;
        int lb = 1;
        if(fir[u]&&v == fir[u]) --lb;
        if(las[u]&&tail[v] == las[u]) ++lb;
        int t = v;
        while(t)
        {
            e[lb].push_back(t);
            t = nxt[t];
        }
    }
    F(i,0,2)
        for(auto j:e[i])
            dfs(j);
}
inline bool check_first(int u,int x)
{
    while(f[u] != x)
    {
        if(fir[f[u]]&&fir[f[u]] != u) return 0;
        if(pre[u]) return 0;
        if(tail[u]&&tail[u] == las[f[u]]&&len[u] != child[f[u]]) return 0;
        u = f[u];
    }
    return 1;
}
inline bool check_last(int u,int x)
{
    while(f[u] != x)
    {
        if(las[f[u]]&&las[f[u]] != u) return 0;
        if(nxt[u]) return 0;
        if(head[u]&&head[u] == fir[f[u]]&&len[head[u]] != child[f[u]]) return 0;
        u = f[u];
    }
    return 1;
}
inline bool check(int u,int v,int x)
{
    while(f[u] != x) u = f[u];
    while(f[v] != x) v = f[v];
    if(nxt[u] == v&&pre[v] == u) return 1;
    if((nxt[u]&&nxt[u] != v)||(pre[v]&&pre[v] != u)) return 0;
    if(head[u] == v&&tail[v] == u) return 0;
    if(fir[x]&&las[x]&&head[u] == fir[x]&&tail[v] == las[x]&&len[head[u]] + len[v] != child[x]) return 0;
    if(u == las[x]||v == fir[x]) return 0;
    return 1;
}
int main()
{
//  freopen("reorder.in","r",stdin);
//  freopen("reorder.out","w",stdout);
    read(n),read(m);
    F(i,1,n)
    {
        cin >> s;
        s.push_back('a'-1);
        int u = 1;
        F(j,0,s.size()-1)
        {
            int ch = s[j]-'a'+1;
            if(!son[u][ch])
            {
                son[u][ch] = ++cnt;
                if(++child[u] >= 2) sum += 1ll * j * j;
            }
            u = son[u][ch];
        }
        ed[u] = i;
        id[i] = u;
    }
    rt = build(1);
    dep[rt] = 1;
    F(i,1,cnt)
    {
        if(f[i]) dep[i] = dep[f[i]] + 1;
        head[i] = tail[i] = i;
        len[i] = 1;
    }
    F(i,1,m) read(p[i].first),read(p[i].second);
    D(i,m,1)
    {
        int u = id[p[i].first],v = id[p[i].second],x = lca(u,v);
        if(check_last(u,x)&&check_first(v,x)&&check(u,v,x))
        {   
            while(f[u] != x)
            {
                las[f[u]] = u;
                u = f[u];
            }
            while(f[v] != x)
            {
                fir[f[v]] = v;
                v = f[v];
            }
            if(pre[v] != u||nxt[u] != v)
            {
                pre[v] = u;
                nxt[u] = v;
                head[tail[v]] = head[u];
                tail[head[u]] = tail[v];
                len[head[u]] += len[v];
                len[v] = 0;
                head[u] = tail[v] = 0;  
            }
            ++ans;
            mark[i] = 1; 
        }
    }
    write(sum),putchar('\n');
    write(ans),putchar(' ');
    F(i,1,m)
        if(mark[i])
            write(i),putchar(' ');
    putchar('\n');
    dfs(rt);
    return 0;
}