Pathway to Hell
All submissions for this problem are available.
Hansel has finally been able to locate Gretel. It is a twisted path that must be traversed to reach her. However time is running out and he has only one lead that might help him determine the shortest route.
The path is represented by a tree having N vertices and N-1 edges. Every vertex is associated with a single letter Li. Hansel's lead is in the form of a string S composed of letters. Choose the two limiting vertices A and B and verify that the shortest route corresponds to the clue S.
The first line is a single integer T denoting the number of test cases.
For every case, the first line is an integer N.
The following N-1 lines contain 2 integers A and B representing the existence of an edge between vertices A and B.
The next line contains a string L of length N representing the letters associated with the N vertices. The last line contains the string S. Both strings L and S consist of lowercase letters only.
For every test case, print "YES" if the clue is valid and "NO" otherwise.
1 ≤ T ≤ 200
1 ≤ N ≤ 104
1 ≤ A,B ≤ N ; A≠B
|C| = N
1 ≤ |S| ≤ 104
2 10 1 2 1 3 1 4 1 5 1 8 2 10 2 6 6 7 4 9 qxlrskmwte trqxkm 10 1 2 1 3 1 4 1 5 1 8 2 10 2 6 6 7 4 9 qxlrskmwte mkqrs
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.