#Pmp18. 2.删边操作

2.删边操作

2.删边操作

题目描述

给定一颗n个点的带点权树,每次删去一条尚未被删去的边,直到得到一个包含n棵只有一个点的树的森林。定义一条简单路径的权值为路径上点权之和,一棵树的直径为树上权值最大的简单路径。求任一时刻他拥有的所有树的直径权值的乘积。因为这个数可能很大,他要求你输出乘积对109+710^9+7取模之后的结果

输入格式

输入的第一行包含一个整数n,表示树T上顶点的数量。

下一行包含n个空格分隔的整数,表示顶点的权值。

之后的n−1行中,每一行包含两个用空格分隔的整数,表示节点和节点之间连有一条边,编号为in-1行中,每一行包含两个用空格分隔的整数,表示节点和节点之间连有一条边,编号为i。

再之后n−1行中,每一行包含一个整数,表示在第jn-1行中,每一行包含一个整数,表示在第j天里会被删除的边的编号。

输出格式

输出包括n行。

在第i行,输出删除i−1条边之后,所有树直径的乘积对109+7i行,输出删除i-1条边之后,所有树直径的乘积对10^9+7取模的结果。

数据范围

(原站未提供,导入后需人工补齐)

样例

3
1 2 3
1 2
1 3
2
1
6
9
6

提示

样例解释

初始,树的直径权值为6(由节点2,1和3构成的路径)。

在第一天之后,得到了两棵直径权值都为3的树。

第二天之后,得到了三棵直径权值分别为1,2,3的树,乘积为6

对于30%的数据,n,m<=103n,m<=10^3。

对于100%的数据,1<=n,m<=105,每个节点的编号都不超过1051<=n,m<=10^5,每个节点的编号都不超过10^5。

。