The Secret Mission
All submissions for this problem are available.Rick is busy working on inventing a new gadget as always. Now, Morty wants him to take a break from his work and accompany him for a secret mission to Dimension 35-C. Rick is in a dilemma as he doesn’t want to leave his work incomplete and also doesn’t want Morty to go on the mission alone. Therefore, he plays a small trick by agreeing to accompany him on a condition wherein he gives a problem to solve Morty so that he gets some time to complete his work. If Morty answers the problem correctly in one go then Rick will accompany him to Dimension 35-C. The problem is: There are $N$ towers in Dimension 35-C numbered from $1$ to $N$. The towers can broadcast their message to selected towers either way rather than sending to all towers at once (i.e. the network of towers forms an undirected connected graph). The task is to sequence the towers in the order in which the message will be received keeping the following rules in mind: - The message is always received by tower $1$ initially. - From tower $1$, it will be broadcasted to the selected (i.e.neighboring) towers - Now the neighboring towers will broadcast the message to their neighboring ones until it reaches to all $N$ towers. - Each tower will broadcast or will receive the message just once. Order of choosing neighbors for a tower may vary hence multiple orderings are possible. Now, Morty has suggested a solution and seeks your help to cross check his answer before submitting his final answer. $Note:-\ It\ is\ guaranteed\ that\ the\ given\ graph\ is\ a\ tree.$ ###Input: - First line contains N ($1 \leq N \leq 2\ .\ 10^5$) Number of towers - Next N-1 lines contain the integers $P\ and\ Q$ wherein $P$ and $Q$ can broadcast the message either way. ($1 \leq P,\ Q \leq N$) - The last line contains the answer of Morty (i.e. sequence of $N$ distinct integers) ###Output: - You task is to output $Yes$ if the answer of Morty is correct and $No$ if it’s incorrect. ###Subtasks - 30 points : $1 \leq N \leq 200$ - 70 points : $Original\ Constraints$ ###Sample Input 1: 7 2 4 2 5 3 6 3 7 1 2 1 3 1 2 3 4 5 6 7 ###Sample Output 1: Yes ###Sample Input 2: 7 2 4 2 5 3 6 3 7 1 2 1 3 1 2 3 6 7 4 5 ###Sample Output 2: No ###Explanation : $1\ 2\ 3\ 4\ 5\ 6\ 7$ and $1\ 3\ 2\ 6\ 7\ 4\ 5$ both are correct. But $1\ 2\ 3\ 6\ 7\ 4\ 5$ is incorrect since neighbors of tower $2$ will receive the message first rather than tower $3$.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions