Company Club Membership

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
You are working in a company with N employees numbered from 0 to N  1, and employee 0 is the director. Each employee, except the director, has a supervisor. The director doesn't have a supervisor. Let's call employee v, an ancestor of employee u if and only if v is the supervisor of u or v is an ancestor of the supervisor of u.
Also, each employee belongs to exactly one club at any moment. Employee i belongs to club number C_{i} initially. The company has assemblies for which all the employees of the company gather. During an assembly, the employees introduce each other, in a particular fashion. Employee v introduces employee a to employee b if a, b, v are from the same club, a is ancestor of v and v is ancestor of b.
Also some employees may change their club. You are given these changes, and you need to calculate the total number of introduces if an assembly was to be held after each such club membership change.
Input
 The first line contains two integers, N and Q, denoting the number of employees in the company and the number of club membership changes, respectively.
 The second line contains N  1 spaceseparated integers: P_{1}, P_{2}, ..., P_{N  1}, denoting the supervisors. P_{i} is the supervisor of employee i.
 The third line contains N spaceseparated integers: C_{0}, C_{1}, ..., C_{N  1}, denoting the clubs. C_{i} is the club that employee i belongs to initially.
 Then, Q lines follow which contain the numbers X_{1}, X_{2}, .., X_{Q}, one in each line. That is, line number i + 3 contains X_{i}. What it denotes is explained below.
The queries are encoded, and have to be decoded online. The ith change (i running from 1 to Q) is that employee number (i  1) mod N changes his club to (X_{i} + ans) mod N. Where ans is the previous output (Note that, even for i = 1, there is a "previous output", because as is explained below, the first output has to be before any change).
Output
You have to output Q + 1 lines. Line number i + 1 should contain the answer for the original company after first i changes. That is, you should output the answer for the original company, and then after each club membership change.
Constraints
 1 ≤ N ≤ 500000
 1 ≤ Q ≤ 500000
 0 ≤ P_{i} < i
 0 ≤ C_{i} < N
 0 ≤ X_{i} < N
Subtasks
 Subtask #1 (30 points): N, Q ≤ 2000
 Subtask #2 (20 points): N ≤ 2000
 Subtask #3 (35 points): N, Q ≤ 100000
 Subtask #4 (15 points): Original constraints
Example
Input: 9 2 0 0 1 1 2 3 3 5 1 0 1 0 2 1 0 0 1 5 8 Output: 6 3 2
Explanation
We represent employee v introducing employee a to employee b, by the triplet (a, v, b).
Initially, before any change, there are a total of 6 introduces. They are:
 (0, 2, 5)
 (0, 2, 8)
 (0, 5, 8)
 (2, 5, 8)
 (1, 3, 6)
 (1, 3, 7)
To decode the first change, we consider (X_{1} + ans) mod N = (5 + 6) mod 9 = 2. So, employee (i  1) mod N = employee 0, changes his club to 2. After this change, the number of introduces reduces. There is no new introduce triplet formed, but the triplets (0, 2, 5), (0, 2, 8) and (0, 5, 8) are no longer valid. Hence, there are only 3 introduces which are:
 (2, 5, 8)
 (1, 3, 6)
 (1, 3, 7)
So the second output is 3, and ans becomes 3 now.
To decode the second change, we consider (X_{2} + ans) mod N = (8 + 3) mod 9 = 2. So, employee (i  1) mod N = employee 1, changes his club to 2. Now, some old introduces are lost, and some new ones formed. The introduces after this change are:
 (2, 5, 8)
 (0, 1, 4)
So the third output is 2.
Author:  grumpy_gordon 
Tester:  lg5293 
Tags  binarysearch, dfs, grumpy_gordon, hard, ltime49, partialsums, segmenttree 
Date Added:  20062017 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions