Skip to content

1116: Forest

题目

题目描述

经过一学期的勤奋学习,侯不会终于掌握了程序设计的知识,他现在会做这道题,但是他想考考你。
一棵有$n$ 个点的树,每个点都有权值。一条简单路径的权值为路径上所有点的权值之和,一棵树的直径为树上权值最大的简单路径。
现在,不断地删去树上的边,每删一次就会多一棵树,请计算出任意时刻所有树的直径的乘积。
这个数可能很大,你只需输出对$10^9+7$ 取模之后的结果。

输入格式

第一行,一个正整数 $n$。
下一行 $n$ 个整数 $a_i$,表示顶点的权值。
之后的 $n-1$ 行,每行两个整数 $u_i$ 和 $v_i$,表示 $u_i$ 和 $v_i$之间的有一条边,编号为 $i$。
再之后 $n-1$ 行,每一行一个整数 $k_j$,表示第 $j$ 条被删除的边的编号。

输出格式

输出共 $n$ 行,第 $i$ 行输出删除 $i-1$ 条边后的结果。

样例输入

3  
1 2 3  
1 2   
1 3   
2  
1

样例输出

6  
9  
6

数据范围

对于100%的数据,$n <= 10^5, a_i <= 10^4$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!