5371: Kanade Loves Maze Designing
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
Kanade is designing a mini-game. It's a puzzle game that orders players to get out of a maze. Players should also collect as many kinds of elements as they can to gain a better score.
For the easy mode, the maze can be described as a tree. There are n crossings and n−1 undirected passages which make the n crossings connected. The n crossings is numbered with integers from 1 to n. Exactly one element is placed on each crossing. The kind of element placed at crossing i is denoted by an integer ci in the range [1,n].
To evaluate the maze's difficulty, Kanade wants to know how many kinds of elements appear on p(u,v) for every two integers u,v∈[1,n]. p(u,v) indicates the simple path from crossing u to crossing v in the maze.
For the easy mode, the maze can be described as a tree. There are n crossings and n−1 undirected passages which make the n crossings connected. The n crossings is numbered with integers from 1 to n. Exactly one element is placed on each crossing. The kind of element placed at crossing i is denoted by an integer ci in the range [1,n].
To evaluate the maze's difficulty, Kanade wants to know how many kinds of elements appear on p(u,v) for every two integers u,v∈[1,n]. p(u,v) indicates the simple path from crossing u to crossing v in the maze.
输入
The first line of input contains one integer T (1≤T≤10), indicating the number of test cases.
For each test case, the first line contains one integer n (2≤n≤2000), indicating the number of crossings in the maze.
The second line contains n−1 integers p2,p3,…,pn (pi<i), indicating that the i-th crossing is connected with the pi-th crossing by a passage.
The third line contains n integers c1,c2,…,cn (1≤ci≤n), indicating that the kind of element placed at crossing i is ci.
It is promised that for all test cases, ∑n≤5000.
For each test case, the first line contains one integer n (2≤n≤2000), indicating the number of crossings in the maze.
The second line contains n−1 integers p2,p3,…,pn (pi<i), indicating that the i-th crossing is connected with the pi-th crossing by a passage.
The third line contains n integers c1,c2,…,cn (1≤ci≤n), indicating that the kind of element placed at crossing i is ci.
It is promised that for all test cases, ∑n≤5000.
输出
For each test case, output n lines. Each line contains two integers. Let ai,j be the number of kinds of elements appear on p(i,j). Let
f(i,x)=$\sum_{j=1}^n$ai,jxj−1
Then for the i-th line, output f(i,19560929)mod(109+7) and f(i,19560929)mod(109+9), space separated.样例输入 复制
1
6
1 1 2 2 3
1 1 4 5 1 4样例输出 复制
495644981 518101442
495644981 518101442
397599492 896634980
612255048 326063507
495644981 518101442
397599492 896634980提示
Let A=(aij), then for the example, A equals to
1 1 2 2 1 2
1 1 2 2 1 2
2 2 1 3 2 1
2 2 3 1 2 3
1 1 2 2 1 2
2 2 1 3 2 1
1 1 2 2 1 2
1 1 2 2 1 2
2 2 1 3 2 1
2 2 3 1 2 3
1 1 2 2 1 2
2 2 1 3 2 1