首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。