题解 CF1312G 【Autocompletion】

xtx1092515503 · 2020-07-23 08:46:16 · 题解

很明显按照题意建出来的东西是一颗trie。

于是我们就设f[i]表示到达字典树上第i个点最少步数。

则我们如果设delta_i表示i节点是树上字典序第delta_i小的节点的话，我们就可以得到转移方程：

上半部可以直接O(1)转移，关键是下半部。

我们可以直接将f[anc]-delta_{anc}压到一个栈中，如果发现新到达的这个点的f[x]-delta_x要小于栈顶的元素，就直接入栈。然后转移时就直接使用栈顶元素即可。当离开一个节点时，弹出它对应的元素（假如那个数还在栈中的话）。

然后我们发现这个delta数组实际上都不用建出来，直接用一个值delta维护即可。

复杂度O(n)。

代码（29行小清新马蜂，你值得拥有）：

#include<bits/stdc++.h>
using namespace std;
int n,m,delta,q[1001000];
struct trie{
    int ch[26],f;
    bool fin;
}t[1001000];
stack<pair<int,int> >s;
void dfs(int x){
    if(s.empty()||t[x].f-delta<s.top().second)s.push(make_pair(x,t[x].f-delta));
    delta+=t[x].fin;
    for(int i=0;i<26;i++){
        if(!t[x].ch[i])continue;
        t[t[x].ch[i]].f=t[x].f+1;
        if(!s.empty()&&t[t[x].ch[i]].fin)t[t[x].ch[i]].f=min(t[t[x].ch[i]].f,s.top().second+delta+1);
        dfs(t[x].ch[i]);
    }
    if(!s.empty()&&s.top().first==x)s.pop();
}
char str[2];
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)scanf("%d%s",&x,str),t[x].ch[str[0]-'a']=i;
    scanf("%d",&m);
    for(int i=1,x;i<=m;i++)scanf("%d",&q[i]),t[q[i]].fin=true;
    dfs(0);
    for(int i=1;i<=m;i++)printf("%d ",t[q[i]].f);
    return 0;
}