Educational Codeforces Round 83 --- G. Autocompletion

解法

题意其实就是用trie的方式给你n个串。f[x]=f[p]+1,p是x的父亲，很显然，添加一个就可以了。我们需要考虑的是，如何通过某个前缀转移到f[x]，就是f[x]=f[t]+rank(t--x)。而所有的t就是这颗trie树从x点到root点这条链上的结点，利用dfs可以维护这条链的信息，我们只需要对每个结点记录一个id，表示在给定的集合S中，这个前缀是第几名，rank(t--x)就是可以通过id[x]和id[t]轻易算出了。

#include <bits/stdc++.h>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;

const int inf = 1e9;
const int maxn = 1e6;
bool vis[maxn + 11];
int x[maxn + 11],f[maxn + 11],nxt[maxn + 11][26],id[maxn + 11];
int n;
int tot = 0;

void dfs(int x,int mn) {
	if (vis[x]) {
		id[x] = ++tot;
		f[x] = min(f[x] , mn + id[x]);
		mn = min(mn , f[x] - id[x] + 1);
	}
	else {
		id[x] = tot;
		mn = min(mn , f[x] - id[x]);
	}
	for (int i = 0; i < 26; i++)
		if (nxt[x][i]) {
			f[nxt[x][i]] = f[x] + 1;
			dfs(nxt[x][i] , mn);
		}
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int p; char c;
		cin >> p >> c;
		nxt[p][c - 'a'] = i;
	}
	int k; cin >> k;
	for (int i = 1; i <= k; i++) {
		cin >> x[i];
		vis[x[i]] = true;
	}
	dfs(0 , 0);
	for (int i = 1; i <= k; i++)
		cout << f[x[i]] << " ";
}