题解：P11179 [ROIR 2018] 管道监控 (Day1)

Meta_Morph · 2025-11-23 15:26:59 · 题解

[ROIR 2018] 管道监控 (Day1) 题解

[ROIR 2018] 管道监控 (Day1) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

Trie，Hash，树形 DP。

分析

其实很容易就可以想到全部解法，考虑 DP。

由于字符串长度较长，肯定有一维需要用来记延后处理的字符串，然后我们发现状态就没别的了，于是设 f_{u,i} 表示 u 节点处选取字符串往上延伸了 i 长度的最小花费。

初始状态为 f_{u,0}=0,f_{u,i}=\inf(i>0)。

这个 DP 分两步走：

合并子树，假设现在合并子节点 v，那么转移方程就为：
f'_{u,\max(i,j)} \gets f_{u,i} + f_{v,j+1} \\
这一步可以 O(n^2) 做，也可以优化到 O(n)。
给自己加字符串。

注：一个字符串只需要在最底下的点加一遍即可，一个点最多也只会作为一个加入的字符串的底部。这两个点比较浅显，但还是解释一下。

如果找到可以加入的字符串，长度为 len，权值为 w，那么我们的转移方程就为：
f'_{u,len} \gets f_{u,i} (i<len) \\
这一步可以 O(n^2) 做，也可以 O(n) 做。

那么考虑如何找符合条件的字符串，可以在 DP 时用栈记录前缀 Hash，复杂度是 O(nm)，可以通过；也可以考虑把所有串倒过来插入 Trie，查询时也倒着往上查，复杂度 O(n^2+|\sum \mathrm{len}(st_k)|)。

最后的方案可以开个数组记一下，然后将 DP 过程整个倒过来做一遍回溯即可。

复杂度可以做到 O(n^2+|\sum \mathrm{len}(st_k)|)。

代码

这里实现的是最劣的 O(n^3+nm)，且由于对 ROIR 的阴影使用了双 Hash，代码冗长，常数巨大（但是也不用卡常），不建议观看。

constexpr int N(500+10),M(1e5+10),S(1e6+10);

namespace Hashs {
    constexpr int P1(1e9+7),P2(1e9+9);
    struct Hash {
        int a,b;
        Hash(int a=0,int b=0):a(a),b(b) {}

        friend Hash operator +(Hash A,Hash B) {
            return Hash(A.a+B.a>=P1?A.a+B.a-P1:A.a+B.a,A.b+B.b>=P2?A.b+B.b-P2:A.b+B.b);
        }
        friend Hash operator -(Hash A,Hash B) {
            return Hash(A.a-B.a<0?A.a-B.a+P1:A.a-B.a,A.b-B.b<0?A.b-B.b+P2:A.b-B.b);
        }
        friend Hash operator *(Hash A,Hash B) {
            return Hash((ll)A.a*B.a%P1,(ll)A.b*B.b%P2);
        }
        friend bool operator ==(Hash A,Hash B) { return A.a==B.a&&A.b==B.b; }
    } pw[N];
    const Hash B(131,13331);

    void Init(const int n=N-5) {
        pw[0]=Hash(1,1);
        FOR(i,1,n)pw[i]=pw[i-1]*B;
    }

    Hash constr(int len,char *s) {
        Hash res(0,0);
        FOR(i,1,len)res=res*B+Hash(s[i]-'a'+1,s[i]-'a'+1);
        return res;
    }
} using namespace Hashs;

int n,m,TYPE;

char pa[N];
int fa[N];
vector<int> g[N];

int w[M],len[M];
Hash h[M];

int self[N][N],Self[N][N];
int Fa_v_u[N][N],Fa_v_v[N][N];
ll f[N][N];

int top;
Hash st[N];

Hash query(int l,int r) { return st[r]-st[l-1]*pw[r-l+1]; }

void DP(int u) {
    f[u][0]=0,self[u][0]=0,Self[u][0]=0;
    FOR(i,1,n)f[u][i]=LINF,self[u][i]=0,Self[u][i]=i;
    if(u!=1)++top,st[top]=st[top-1]*B+Hash(pa[u]-'a'+1,pa[u]-'a'+1);
    for(int v:g[u]) {
        DP(v);
        static ll tmp[N];
        FOR(i,0,n)tmp[i]=LINF;
        FOR(i,0,n)if(f[u][i]<LINF)FOR(j,0,n)if(f[v][j+1]<LINF) {
            const int k(max(i,j));
            if(tmp[k]>f[u][i]+f[v][j+1])
                tmp[k]=f[u][i]+f[v][j+1],Fa_v_u[v][k]=i,Fa_v_v[v][k]=j+1;
        }
        FOR(i,0,n)f[u][i]=tmp[i];
    }
    static int mark[N];
    FOR(i,1,top)mark[i]=-1;
    FOR(i,1,m)if(len[i]<=top&&query(top-len[i]+1,top)==h[i]) {
        if(!~mark[len[i]]||w[i]<w[mark[len[i]]])mark[len[i]]=i;
    }
    FOR(i,1,top)if(~mark[i])FOR(j,0,i)if(f[u][i]>f[u][j]+w[mark[i]])
        f[u][i]=f[u][j]+w[mark[i]],self[u][i]=mark[i],Self[u][i]=j;
    if(u!=1)--top;
}

int St[N];
vector<tuple<int,int,int>> Ans;

void DFS(int u,int i) {
    St[++top]=u;
    if(self[u][i]) {
        int t(self[u][i]);
        Ans.push_back({St[top-len[t]],u,t}),i=Self[u][i];
    }
    int siz(g[u].size());
    DOR(p,siz-1,0) {
        int v(g[u][p]);
        DFS(v,Fa_v_v[v][i]),i=Fa_v_u[v][i];
    }
    --top;
}

signed main() {
    /*DE("Input");*/
    scanf("%d%d%d",&n,&m,&TYPE),Init();
    // check
    if(n==1) {
        puts("0");
        if(TYPE)puts("0");
        return 0;
    }
    // build
    FOR(i,2,n) {
        static char opt[3];
        scanf("%d%s",&fa[i],opt),g[fa[i]].push_back(i),pa[i]=*opt;
    }
    // hash
    FOR(i,1,m) {
        static char opt[S];
        scanf("%d%s",&w[i],opt+1),len[i]=strlen(opt+1);
        if(len[i]>n-1)continue;
        h[i]=constr(len[i],opt);
    }
    /*DE("DP");*/
    DP(1);
    if(f[1][0]>=LINF)return puts("-1"),0;
    printf("%lld\n",f[1][0]);
    if(TYPE) {
        DFS(1,0),printf("%d\n",(int)Ans.size());
        for(const auto &p:Ans)printf("%d %d %d\n",get<0>(p),get<1>(p),get<2>(p));
    }
    return 0;
}