Problem 3790 --Kanade Loves Maze Designing3790: Kanade Loves Maze Designing
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$128$ 兆字节/Megabyte(s) |
| 提交总数 |
$0$ |
正确数量 |
$0$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
搜索 |
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.
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, 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)=∑nj=1 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
| 本题记录 |
用 户(点击查看用户) |
运行号(点击购买题解) |
时 间 |
| 算法最快[$0 $ms]
|
|
0
|
|
| 内存最少[$0 $KB]
|
|
0 |
|
| 第一AC |
|
0
|
|
| 第一挑战 |
|
0 |
|
赛题来源/所属竞赛
N/A