【标题问题描述】
萌萌买了一颗字符串树的种子，春天种下去以后夏天就能长出一棵很大的字符串树。字符串树很独特，树枝上都密密麻麻写满了字符串，看上去很庞大的样子。
字符串树素质上还是一棵树，即N个节点N-1条边的连通无向无环图，节点从1到N编号。与普通的树差此外是，树上的每条边都对应了一个字符串。萌萌和JYY在树下玩的时候，萌萌决定考一考JYY。每次萌萌都写出一个字符串S和两个节点U,V，需要JYY当即回答U和V之间的最短路径（即,之间边数最少的路径。由于给定的是一棵树，这样的路径是独一的）上有几多个字符串以为前缀。
JYY虽然精通编程，但对字符串措置惩罚惩罚却不在行。所以他请你帮他解决萌萌的难题。

【输入格局】
输入第一行包罗一个整数N，代表字符串树的节点数量。
接下来N-1行，每行先是两个数U,V，，然后是一个字符串S,暗示节点和U节点V之间有一条直接相连的边，这条边上的字符串是S。输入数据保证给出的是一棵合法的树。
接下来一行包罗一个整数Q，暗示萌萌的问题数。
接来下Q行，每行先是两个数U,V，然后是一个字符串S,暗示萌萌的一个问题是节点U和节点V之间的最短路径上有几多字符串以S为前缀。

【输格外式】
输出Q行，每行对应萌萌的一个问题的答案。

题解
前置常识点: 可长期化Trie 树链剖分/LCA

可长期化Trie撑持查找一段区间内的所有字符串的相关信息
在此题中可以树链剖分后盘问路径上的字符串有几多个包罗有询问的前缀
码量稍大 其实就是道模板题 时间庞大度\(O(q\ log\ n)\)

也可以直接用LCA做 免去了树剖 建Trie树时令以当前节点i代表的树从历史版本fa[i]转移过来 然后询问x~y的路径就用 树x + 树y - 树lca 就行了 实现更简单一点

代码

#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); return x * f; } int n, m, tot; int head[100005], pre[200005], to[200005], len[200005], sz; char s[200005][11], q[11]; inline int o(char ch) { return ch - 'a' + 1; } inline void addedge(int u, int v) { pre[++sz] = head[u]; head[u] = sz; to[sz] = v; pre[++sz] = head[v]; head[v] = sz; to[sz] = u; } namespace Trie{ struct trie{ int son[30], sz; } tr[5000005]; int rt[100005]; void insert(int d, int &ind, int lst, char *str) { ind = ++tot; tr[ind].sz = tr[lst].sz; if (str[d] < 'a' || str[d] > 'z') { tr[ind].sz++; return; } for (int i = 1; i <= 26; i++) { tr[ind].son[i] = tr[lst].son[i]; } insert(d+1, tr[ind].son[o(str[d])], tr[lst].son[o(str[d])], str); for (int i = 1; i <= 26; i++) { tr[ind].sz += tr[tr[ind].son[i]].sz - tr[tr[lst].son[i]].sz; } } int query(int d, int lind, int rind, char *str) { if (str[d] < 'a' || str[d] > 'z') { return max(0, tr[rind].sz - tr[lind].sz); } else return query(d+1, tr[lind].son[o(str[d])], tr[rind].son[o(str[d])], str); } } using namespace Trie; namespace Treechains{ int d[100005], dfn[100005], rnk[100005], tme, fa[100005], top[100005], siz[100005], son[100005], sonind[100005]; void dfs(int x, int fafa) { siz[x] = 1; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fafa) continue; d[y] = d[x] + 1; fa[y] = x; dfs(y, x); siz[x] += siz[y]; if (!son[x] || siz[y] > siz[son[x]]) son[x] = y, sonind[x] = i; } } void dfs2(int x, int tp) { dfn[x] = ++tme; rnk[tme] = dfn[x]; top[x] = tp; if (son[x]) { insert(1, rt[tme+1], rt[tme], s[sonind[x]]); dfs2(son[x], tp); } for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa[x] || y == son[x]) continue; insert(1, rt[tme+1], rt[tme], s[i]); dfs2(y, y); } } inline int query_path(int x, int y) { int ret = 0; while (top[x] != top[y]) { if (d[top[x]] < d[top[y]]) swap(x, y); ret += query(1, rt[dfn[top[x]]-1], rt[dfn[x]], q); x = fa[top[x]]; } if (d[x] > d[y]) swap(x, y); ret += query(1, rt[dfn[x]], rt[dfn[y]], q); return ret; } } using namespace Treechains; int main() { n = read(); for (int i = 1; i < n; i++) { addedge(read(), read()); scanf("%s", s[sz-1]+1); len[sz-1] = len[sz] = strlen(s[sz-1]+1); for (int j = 1; j <= len[sz-1]; j++) s[sz][j] = s[sz-1][j]; } dfs(1, 0); dfs2(1, 1); m = read(); for (int i = 1; i <= m; i++) { int x = read(), y = read(); scanf("%s", q+1); query_path(x, y); printf("%d\n", query_path(x, y)); } return 0; }

字符串树「JSOI2015」