首页 > 代码库 > LibieOJ 6170 字母树 (Trie)

LibieOJ 6170 字母树 (Trie)

题目链接 字母树

(以每个点为根遍历,插入到trie中,统计答案即可)——SamZhang

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)typedef long long LL;const int N = 5010;struct node{	int son[26];	int cnt, tot;	int sum[27];} trie[N];int n, m, q;vector <int> v[N];vector <char> ch[N];int ans[N][N];void build_trie(int x, int fa, int p){	++trie[p].cnt;	int i = -1;	for (auto u : v[x]){		++i;		if (u == fa) continue;		int c = ch[x][i] - ‘a‘;		if (trie[p].son[c] == 0){			++m;			trie[p].son[c] = m;		}		build_trie(u, x, trie[p].son[c]);	}}void get_answer(int x, int fa, int p, int cnt, int ans[]){	ans[x] = cnt;	cnt += trie[p].cnt;	int i = -1;	for (auto u : v[x]){		++i;		if (u == fa) continue;		int c = ch[x][i] - ‘a‘;		get_answer(u, x, trie[p].son[c], cnt + trie[p].sum[c], ans);	}}int main(){	scanf("%d%d", &n, &q);	rep(i, 1, n - 1){		int x, y;		char z[10];		scanf("%d%d%s", &x, &y, z);		v[x].push_back(y);		v[y].push_back(x);		ch[x].push_back(z[0]);		ch[y].push_back(z[0]);	}	rep(i, 1, n){		m = 0;		memset(trie, 0, sizeof trie);		build_trie(i, 0, 0);		dec(j, m, 0){			trie[j].tot = trie[j].cnt;			rep(k, 0, 25){				trie[j].sum[k + 1] = trie[j].sum[k];				if (trie[j].son[k] > 0){					trie[j].tot += trie[trie[j].son[k]].tot;					trie[j].sum[k + 1] += trie[trie[j].son[k]].tot;				}			}			rep(k, 1, 25){				trie[trie[j].son[k - 1]].cnt;			}		}		get_answer(i, 0, 0, 0, ans[i]);	}	while (q--){		int x, y;		scanf("%d%d", &x, &y);		printf("%d\n", ans[x][y] - 1);	}	return 0;}

 

LibieOJ 6170 字母树 (Trie)