Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | christmas-balls.in, christmas-balls.out | Sursă | IIOT 2021-22 Runda 2 |
| Autor | Edoardo Morassutto | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 256144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Christmas Balls
Christmas is coming, and Alessandro has to decorate his living room with a Christmas tree.
He heard that in Pordenone a new tree shop has just opened, so he decided to go there. This shop has a huge tree decorated with N balls, one at each branching point (the root is node 0). Of course the balls are quite spectacular, and he noticed that the balls come in C different colors in total.
The peculiarity of this shop is that you can buy the whole tree, or cut a branch and buy just a subtree! You can make the cut just below a ball, so that you take that ball and the subtree rooted there.
Alessandro doesn't want just a random tree, he wants the nicest. His taste is in fact quite peculiar, he'd like that the amount of balls of each color to be well distributed. Precisely, let's call x the number of balls of (one of) the most frequent color in a subtree, he wants to maximize the number of colors with x balls each.
Help Alessandro finding where to cut the tree by printing the maximum amount of most-frequent colors he can get.
Date de intrare
The first line of the input file christmas-balls.in contains the only integer N, 1 ≤ N ≤ 10^5, the number of nodes of the tree.
The second line contains N integers C_i 0 ≤ C_i < N, the colors of each ball.
The third line contains N-1 integers: P_i (with 1 ≤ i < N) is the index of the parent of the i-th node.
Date de ieşire
The output file christmas-balls.out contains a single line with an integer: chosen the optimal subtree, the number of colors with the highest frequency.
Restrictii
- For tests worth 13 points, the tree is a line.
- For tests worth 15 more points, 1 ≤ N ≤ 1000, 1 ≤ MAXC ≤ 2.
- For tests worth 21 more points, 1 ≤ N ≤ 1000.
- For tests worth 17 more points, 1 ≤ MAXC ≤ 2.
- The scores obtained now may be different compared to the ones from the original contest
Exemplu
| christmas-balls.in | christmas-balls.out |
|---|---|
| 8 1 2 0 2 0 0 1 1 0 0 1 1 3 4 4 | 3 |
| christmas-balls.in | christmas-balls.out |
|---|---|
| 5 0 1 1 0 0 0 1 2 3 | 2 |
Explicaţie
In the first sample case, there are 8 nodes in 3 different colors. The solution is to cut the tree and take the subtree rooted at node 1. This way we are left with 6 nodes: the most frequent color has 2 balls, and there are 3 colors with that many balls.
If, for example, we have kept the entire tree, the most frequent color appears with 3 balls, but there are only 2 colors with 3 balls, so this is worse than the aforementioned solution.
In the second sample case the tree forms a line with 5 nodes. The optimal solution is to cut the subtree rooted at node 1. The most frequent color appears with 2 balls, and there are 2 colors with that many balls.
