Company and Club Hierarchies

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. Employee i belongs to club number C_{i}. And each club has some internal levels, which are actually independent of the company hierarchy. Each member of a club has a Level Number. The Level Number of employee i is denoted by K_{i}. The higher the Level Number, the more important he is in the club.
Each club wants to advertise, and for that, they want to claim that people who are more important in their club, end up being superior in the company. So they want to find such instances. More precisely, for every employee v, a sequence of company employees (e_{1}, e_{2}, ..., e_{q}) is a good sequence starting at v, if all of these conditions hold true:
 e_{1} = v.
 All of them are part of the same club.
 e_{i} is an ancestor of e_{i+1}, for i = 1 to q  1.
 K[e_{1}] = q  1, K[e_{2}] = q  2, ..., K[e_{q}] = 0.
For each employee v, you want to find the total number of good sequences starting with it. As these numbers could be very large, output the answers modulo 10^{9}+7.
Input
 The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
 The first line of each test case contains two integers, N and X, denoting the number of employees in the company and a bound on the size of the Level Numbers, as mentioned in the Constraints section below.
 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.
 The fourth line contains N spaceseparated integers: K_{0}, K_{1}, ..., K_{N  1}, denoting the Level Numbers. K_{i} is the Level number of employee i.
Output
For each test case, you have to output N lines. Line number i + 1 should contain the answer for employee i.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 500000
 1 ≤ X ≤ N
 0 ≤ P_{i} < i
 0 ≤ C_{i} < N
 0 ≤ K_{i} < X
 1 ≤ Sum of N over all test cases ≤ 1000000
Subtasks
Subtask #1 (20 points):
 Sum of integers in the output of all testcases ≤ 20000, and
 Sum of N over all test cases ≤ 5000
Subtask #2 (30 points):
 N ≤ 5000, and
 Sum of N over all test cases ≤ 20000
Subtask #3 (25 points):
 N ≤ 100000, and
 Sum of N over all test cases ≤ 500000
Subtask #4 (25 points):
 Original constraints
Example
Input: 1 5 3 0 1 2 3 0 0 0 0 0 2 1 1 0 0 Output: 4 2 2 1 1
Explanation
 Good sequences starting at employee 0: (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4)
 Good sequences starting at employee 1: (1, 3), (1, 4)
 Good sequences starting at employee 2: (2, 3), (2, 4)
 Good sequences starting at employee 3: (3)
 Good sequences starting at employee 4: (4)
Author:  admin3 
Tester:  lg5293 
Editorial  https://discuss.codechef.com/problems/COMPCLUB 
Tags  admin3, dfs, dp+trees, dynamicprogramming, ltime49, medium 
Date Added:  23062017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, 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.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 