标签：

「JSOI2015」字符串树

传送门

显然可以树上差分。

我们对付树上每一条从根出发的路径都开一 棵 \(\text{Trie}\) 树，，那么我们就只需要在 \(\text{Trie}\) 树中插入一个字符串时把颠末的节点都加 \(1\) 就好了，但是直接开空间会炸失所以加一个可长期化。

还有一个小问题：我们读入的时候，如果用 char* 来存一条边上的字符串，那么每次都要用差此外 char[] 来传值，不然你就会发明每次的边的值都没变，可能是指针的一些原因吧。

#include <cstring> #include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) template < class T > inline void swap(T& a, T& b) { T t = a; a = b; b = t; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 1e5 + 5; char s[_][15]; int tot, head[_]; struct Edge { int v, nxt; char* s; } edge[_ << 1]; inline void Add_edge(int u, int v, char* s) { edge[++tot] = (Edge) { v, head[u], s }, head[u] = tot; } int n, m, dep[_], siz[_], son[_], fa[_], top[_]; int tt, rt[_]; struct node { int val, son[26]; } t[_ << 5]; inline void insert(int& p, int q, int x, int len, char* s) { t[p = ++tt] = t[q], ++t[p].val; if (x <= len) insert(t[p].son[s[x] - 'a'], t[q].son[s[x] - 'a'], x + 1, len, s); } inline int query(int p, char* s) { int len = strlen(s + 1); for (rg int i = 1; i <= len; ++i) p = t[p].son[s[i] - 'a']; return t[p].val; } inline void dfs(int u, int f) { dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v; if (v == f) continue ; insert(rt[v], rt[u], 1, strlen(edge[i].s + 1), edge[i].s); dfs(v, u), siz[u] += siz[v]; if (siz[son[u]] < siz[v]) son[u] = v; } } inline void dfs(int u, int f, int topf) { top[u] = topf; if (son[u]) dfs(son[u], u, topf); for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v; if (v == f || v == son[u]) continue ; dfs(v, u, v); } } inline int LCA(int x, int y) { int fx = top[x], fy = top[y]; while (fx != fy) { if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy); x = fa[fx], fx = top[x]; } return dep[x] < dep[y] ? x : y; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n); for (rg int u, v, i = 1; i < n; ++i) read(u), read(v), scanf("%s", s[i] + 1), Add_edge(u, v, s[i]), Add_edge(v, u, s[i]); dfs(1, 0), dfs(1, 0, 1); read(m); for (rg int u, v; m--; ) { read(u), read(v), scanf("%s", s[0] + 1); printf("%d\n", query(rt[u], s[0]) + query(rt[v], s[0]) - 2 * query(rt[LCA(u, v)], s[0])); } return 0; }

「JSOI2015」字符串树