题解 CF1312G 【Autocompletion】
xtx1092515503
2020-07-23 08:46:16
很明显按照题意建出来的东西是一颗trie。
于是我们就设$f[i]$表示到达字典树上第$i$个点最少步数。
则我们如果设$delta_i$表示$i$节点是树上字典序第$delta_i$小的节点的话，我们就可以得到转移方程：
$$f[i]=\max\begin{cases}f[fa]+1\\f[anc]-delta_{anc}+delta_i\end{cases}$$
上半部可以直接$O(1)$转移，关键是下半部。
我们可以直接将$f[anc]-delta_{anc}$压到一个栈中，如果发现新到达的这个点的$f[x]-delta_x$要小于栈顶的元素，就直接入栈。然后转移时就直接使用栈顶元素即可。当离开一个节点时，弹出它对应的元素（假如那个数还在栈中的话）。
然后我们发现这个$delta$数组实际上都不用建出来，直接用一个值$delta$维护即可。
复杂度$O(n)$。
代码（29行小清新马蜂，你值得拥有）：
```cpp
#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;
}
```