#Pmp18. 2.删边操作
2.删边操作
2.删边操作
题目描述
给定一颗n个点的带点权树,每次删去一条尚未被删去的边,直到得到一个包含n棵只有一个点的树的森林。定义一条简单路径的权值为路径上点权之和,一棵树的直径为树上权值最大的简单路径。求任一时刻他拥有的所有树的直径权值的乘积。因为这个数可能很大,他要求你输出乘积对取模之后的结果
输入格式
输入的第一行包含一个整数n,表示树T上顶点的数量。
下一行包含n个空格分隔的整数,表示顶点的权值。
之后的。
再之后天里会被删除的边的编号。
输出格式
输出包括n行。
在第取模的结果。
数据范围
(原站未提供,导入后需人工补齐)
样例
3
1 2 3
1 2
1 3
2
1
6
9
6
提示
样例解释
初始,树的直径权值为6(由节点2,1和3构成的路径)。
在第一天之后,得到了两棵直径权值都为3的树。
第二天之后,得到了三棵直径权值分别为1,2,3的树,乘积为6
对于30%的数据,。
对于100%的数据,。
。