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 christmasballs.in contains the only integer N ($1 \le N \le 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.
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$).
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.
Exemplu
| christmasballs.in | christmasballs.out |
|---|---|
| 8 1 2 0 2 0 0 1 1 0 0 1 1 3 4 4 | 3 |
| christmasballs.in | christmasballs.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.
