526互联

CodeForces 1312G Autocompletion

发布时间 2024-01-12 09:27:30作者: zltzlt

洛谷传送门

CF 传送门

考虑直接在题目给的 Trie 上 dp，设 \(f_u\) 为打出 \(u\) 结点的串的最小代价。

  • 首先我们有 \(f_u \gets f_{fa_u} + 1\)。
  • 我们有 \(f_u \gets \min\limits_v f_v + t + 1\)，要求 \(u\) 是某个串的终止结点，\(v\) 是 \(u\) 的祖先，\(t\) 是字典序大于等于 \(v\)，小于 \(u\) 的串的个数。

发现我们可以把 \(f_u\) 扔进一个可删堆里，每个点按字典序遍历对应的子结点，每次经过一棵子树就给这个堆打一个整体加这棵子树大小的 tag。这个可以直接用一个变量维护 tag。

时间复杂度 \(O(n \log n)\)。

code 
// Problem: G. Autocompletion
// Contest: Codeforces - Educational Codeforces Round 83 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1312/G
// Memory Limit: 512 MB
// Time Limit: 7000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;

int n, ch[maxn][26], nt, a[maxn], f[maxn], m, b[maxn], sz[maxn];
bool vis[maxn];

void dfs(int u) {
	for (int i = 0; i < 26; ++i) {
		if (ch[u][i]) {
			dfs(ch[u][i]);
			sz[u] += sz[ch[u][i]];
		}
	}
}

struct Heap {
	priority_queue< int, vector<int>, greater<int> > q1, q2;
	
	inline void insert(int x) {
		q1.push(x);
	}
	
	inline void erase(int x) {
		q2.push(x);
	}
	
	inline int query() {
		while (q1.size() && q2.size() && q1.top() == q2.top()) {
			q1.pop();
			q2.pop();
		}
		return q1.top();
	}
} Q;

int tag;

void dfs2(int u) {
	if (vis[u]) {
		f[u] = min(f[u], Q.query() + tag + 1);
	}
	Q.insert(f[u] - tag);
	tag += vis[u];
	for (int i = 0; i < 26; ++i) {
		if (ch[u][i]) {
			f[ch[u][i]] = f[u] + 1;
			dfs2(ch[u][i]);
			tag += sz[ch[u][i]];
		}
	}
	tag -= vis[u];
	for (int i = 0; i < 26; ++i) {
		if (ch[u][i]) {
			tag -= sz[ch[u][i]];
		}
	}
	Q.erase(f[u] - tag);
}

void solve() {
	scanf("%d", &n);
	for (int i = 1, p; i <= n; ++i) {
		char s[9];
		scanf("%d%s", &p, s);
		p = a[p];
		int t = s[0] - 'a';
		if (!ch[p][t]) {
			ch[p][t] = ++nt;
		}
		a[i] = ch[p][t];
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d", &b[i]);
		++sz[a[b[i]]];
		vis[a[b[i]]] = 1;
	}
	dfs(0);
	dfs2(0);
	for (int i = 1; i <= m; ++i) {
		printf("%d ", f[a[b[i]]]);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}