当前没有测试数据。

2.删边操作

题目描述

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

输入格式

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

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

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

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

输出格式

输出包括$n$行。

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

数据范围与提示

• 对于$30\%$的数据，$n$，$m \leq 10^{3}$；
• 对于$100\%$的数据，$1 \leq n,m \leq 10^{5}$，每个节点的编号都不超过$10^{5}$。

样例

3
1 2 3
1 2
1 3
2
1

6
9
6

说明

初始，树的直径权值为$6$（由节点$2$,$1$和$3$构成的路径）。

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

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