UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4713. 迷失的字符串

Statistics 下载数据

Description

有一棵n个节点的大树,上面每条边有一个小写字符。
对于任意两个不同的点u,v,我们可以在树上找到u出发到v终止的唯一的一条最短路径,并将沿途经过的边上的字符依次写下来,得到一个字符串。
对于一个字符串,如果存在这样一个点对(u,v),使得它们路径上的字符串与其完全匹配,那么我们就称这个字符串属于这棵树。
现在有m个迷失的字符串,请你写一个程序帮助判断每一条字符串是否属于这棵树。

Input

第一行包含一个正整数n(2<=n<=30000),表示树的点数。
接下来n-1行每行包含两个正整数a,b和一个小写字符c(1<=a,b<=n,a!=b),表示a点到b点之间有一条无向的树边,上面写着字符c。
接下来一行包含一个正整数m(1<=m<=30000),表示迷失的字符串的个数。
接下来m行,每行一个由小写字符组成的字符串,分别表示每个迷失的字符串。
输入数据保证所有迷之的字符串的长度之和不超过30000。

Output

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

Sample Input

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

Sample Output

YES
YES
YES
YES
NO
NO
YES
YES
YES

Hint

Source

By Claris