#P4713. 迷失的字符串

    ID: 3839 传统题 1000ms 512MiB 尝试: 384 已通过: 50 难度: 8 上传者: 标签>CF2500提高+/省选-树形 DP位集加速字符串匹配保留重儿子贡献

迷失的字符串

题目描述

有一棵 nn 个节点的大树,上面每条边有一个小写字符。

对于任意两个不同的点 u,vu,v,我们可以在树上找到 uu 出发到 vv 终止的唯一的一条最短路径,并将沿途经过的边上的字符依次写下来,得到一个字符串。

对于一个字符串,如果存在这样一个点对 (u,v)(u,v),使得它们路径上的字符串与其完全匹配,那么我们就称这个字符串属于这棵树。

现在有m个迷失的字符串,请你写一个程序帮助判断每一条字符串是否属于这棵树。

输入格式

第一行包含一个正整数 n(2≤n≤30000)n(2\le n\le 30000),表示树的点数。

接下来 n−1n-1 行每行包含两个正整数 a,ba,b 和一个小写字符 c(1≤a,b≤n,a≠b)c(1\le a,b\le n,a\neq b),表示 aa 点到 bb 点之间有一条无向的树边,上面写着字符 cc。

接下来一行包含一个正整数 m(1≤m≤30000)m(1\le m\le 30000),表示迷失的字符串的个数。

接下来 mm 行,每行一个由小写字符组成的字符串,分别表示每个迷失的字符串。

输入数据保证所有迷之的字符串的长度之和不超过 3000030000。

输出格式

包含 mm 行,对于第 ii 行,如果在树上可以找到第 ii 个字符串,输出 YES,否则输出 NO。

4
1 2 b
1 4 a
2 3 c
9
bc
cb
b
c
d
aa
ab
abc
cba
YES
YES
YES
YES
NO
NO
YES
YES
YES