Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ստուգել BFS-ի շրջանցման վավերությունը

Տրված է ծառ (գրաֆ, որը չունի ցիկլեր) n գագաթներով, ինչպես նաև BFS (Լայնությամբ որոնում) ալգորիթմի արդյունքում ստացված այցելությունների հերթագայությամբ։ Ձեզ խնդրում են ստուգել, արդյոք այդ այցելությունների հերթագայությունը հնարավոր է։

Ալգորիթմը միշտ սկսում է 1-ին գագաթից և անցնում է հարևանների վրայով առանց հատուկ հերթագայության։ Ծրագիրը ելքում պետք է տպի Yes, եթե տվյալ ծառի պարագայում նշված շրջանցումը հնարավոր է, իսկ հակառակ դեպքում – No։

Հիշեցնենք, որ յուրաքանչյուր ծառում կա בדיוק n-1 կող։

Մուտք

Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤ 100000):

Հաջորդ n-1 տողերից յուրաքանչյուրում տրված են զույգ整数եր (1 ≤ ≤ n), որոնք ներկայացնում են ծառի կողերը:

Այնուհետև տրված է մեկ տող, որտեղ կան n բացատով առանձնացված整数եր (1 ≤ ≤ n), որոնք ցույց են տալիս BFS ալգորիթմի այցելությունների հերթագայությունը:

Ելք

Ծրագիրը պետք է տպի Yes, եթե նկարագրված շրջանցումը վավեր է, իսկ հակառակ դեպքում – No:

Օրինակներ

Մուտք

Ելք

4
1 2
1 3
2 4
1 2 3 4

Yes

4
1 2
1 3
2 4
1 2 4 3

No

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue