8713: BZOJ4713：迷失的字符串

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

输入格式

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

输出格式

包含m行，对于第i行，如果在树上可以找到第i个字符串，输出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

提示

没有写明提示

题目来源

By Claris