Description

Input

Output

输出文件名为 call.out。

Sample Input

Sample Input1
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3


Sample Input2
10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3
 

Sample Output

Sample Output1
6 8 12 


Sample Output2
36 282 108 144 180 216 504 288 324 360 
 

Data Constraint

Solution

考虑计算每个加函数对答案的贡献。模拟下暴力的过程，显然它的贡献取决于操作它之后会乘多少。

先对于每个节点，计算出包含它的最小闭合子图（类比子树）的乘积，记作 p i。

对于某个节点 u，从后往前枚举边 v i，可以发现对 v i 的贡献为     。不过这个只是在包含 u 的最小闭 合子图中的贡献，实际上的贡献还要乘上u 的调用次数。

于是具体的做法就出来了：按照拓扑序来做，每个节点上记个 tag i ，表示i 的调用次数。做到节点 u 时，枚举边算贡献，乘上tag i ，然后加到贡献到的节点上去。

时间复杂度是线性的。

Code