All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sergey recently got back from his TreeLand journey.
As you might have probably guessed, TreeLand is a country located far to the east from ByteLand, the country he lives in. As you might have also probably guessed, it is called TreeLand, because historically the road system of the country forms a tree. So, there are N cities in the country and N-1 bidirectional roads, connecting them. The cities are numbered from 1 to N. Of course, it is possible to get from any city of the country to any other city via these roads.
Not long ago, a new King came to the throne in TreeLand. The first thing he had done was re-organizing the road system of the country. It was considered that cities with more than 8 adjacent roads might cause disruption in the road system, because of the high traffic load. So now, every city in TreeLand is directly connected with no more than 8 cities.
Usually, when Sergey travels to the country, he visits all its cities. So now he visited all the N cities of TreeLand. Any time he first visited a city, he wrote its number in his notebook. Eventually, there was a sequence of N integers in the notebook.
But what Sergey didn't know was that it was rainy season in TreeLand, and he was not prepared for it. Sadly, his notebook got wet, and the records became obscure.
Sergey wants to tell his friends about the journey, and so he wants to restore the order in which he visited the cities. He has partially restored his records: for some cities he is certain about when he visited them. He is also certain that he did not wander around wasting his time: he started from some city, visited all the cities and got back to the starting city, and did all this by travelling along the minimum possible number of roads (If he travelled along some road multiple times, it's counted multiple times).
Sergey found a map of the road system of TreeLand. After seeing it, he realized that generally there is more than one way to accomplish his trip. So now he is interested in the number of ways to complete the trip so that it doesn't contradict his records.
Please help him to calculate this number. Since it can be large, output it modulo 109+7.
The first line of the input contains an integer N denoting the number of cities in TreeLand.
The second line contains N space-separated integer numbers. Let's denote the ith of them by Ai. If Ai is 0, then Sergey is not certain about the number of the city that was the ith in his records. Otherwise, Ai denotes the number of the ith city in Sergey's records.
Each of the following N-1 lines contains two space-separated integers, Xj Yj, denoting a road in TreeLand.
Output the total number of possible trips Sergey could have done, which do not contradict the restored records. Since this number can be large, output it modulo 109+7.
- 1 ≤ N ≤ 500
- 0 ≤ Ai ≤ N
- 1 ≤ Xj, Yj ≤ N
- Every city is directly connected with no more than 8 other cities.
- The road system forms a tree.
- There is at least 1 legal way to restore the trip.
Input: 5 1 0 0 0 0 1 2 1 3 3 4 3 5 Output: 4
Sergey could have obtained the following sequences:
- 1 2 3 4 5: 1 -> 2 -> 1 -> 3 -> 4 -> 3 -> 5 -> 3 -> 1.
- 1 2 3 5 4: 1 -> 2 -> 1 -> 3 -> 5 -> 3 -> 4 -> 3 -> 1.
- 1 3 4 5 2: 1 -> 3 -> 4 -> 3 -> 5 -> 3 -> 1 -> 2 -> 1.
- 1 3 5 4 2: 1 -> 3 -> 5 -> 3 -> 4 -> 3 -> 1 -> 2 -> 1.
Here, all the trips have a length of 8 roads. No other trip has length less than or equal to 8 roads.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.