「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」字符串树

「JSOI2015」字符串树

最新文章

热门文章