Santa's Wrath

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Java 2.5s
Python 4.0s
Memory limit: 128M
Java 256M
Python 512M

Problem types

After much hard work, you find the North Pole to be more than adequately prepared for the upcoming Christmas. However, when you go to ask Santa about his retirement, he reveals that he had tricked you and only wanted you to do his work for him. Furious, you challenge him to a present-making duel on Christmas Eve, with the winner attaining the title of Santa.

During the duel, you are responsible for making presents for a big city with N families numbered 1 to N. In this city, there is a hierarchy structure that indicates the prestige of each family. The prestigious family 1 is the most renowned of these families and has every other family somewhere below it. All the other families each have exactly one family directly above them in prestige. At the start, each family has some amount of kids c_i.

To beat Santa, your toy factory must be able to answer the following queries:

  1. 1 x v: Through a Christmas miracle, family x gains v kids.
  2. 2 x v: The kids in family x and every family below them on the hierarchy become obsessed with a new toy. However, this new toy can only be manufactured in bundles of v. You must count and output the number of families in this group that have a number of kids divisible by v.

As spectators begin to gather in the distance, you must now find a way to answer these queries quickly in order to finally realize your dream of becoming Santa.

Input Specification

The first line of input contains two space-separated integers, N and Q.

The next line of input contains N space-separated integers, p_1, p_2, ..., p_N, where p_1 = 0 and p_i is the family above family i.

The next line of input contains N space-separated integers, c_1, c_2, ..., c_N.

The next Q lines of input each contain three space-separated integers, corresponding to one of the above query types.

Output Specification

For each query of type 2, output the answer on a separate line.


For this problem, you are not required to pass previous subtasks to earn points for a specific subtask.

In all subtasks,

1 \le N, Q \le 10^5

1 \le p_i, x \le N

1 \le c_i, v \le 2\cdot 10^4

At any point, the number of kids a family has will not exceed 10^7.

Subtask 1 [10%]

1 \le N, Q \le 10^3

Subtask 2 [30%]

For all type 2 queries, v = 2.

Subtask 3 [60%]

No additional constraints.

Sample Input

8 9
0 3 4 7 8 5 1 7
17420 6186 13022 9244 7696 3496 17956 3528
1 1 1
2 7 4
2 1 3
1 5 3
1 8 4
2 5 1
1 1 4
1 7 3
2 5 8

Sample Output



There are no comments at the moment.