Product of Diameters

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef had a tree T with weighted nodes.
One day he decided that he wants to have two trees instead of one. So, he removed one of the edges of T.
The next day, he decided to have three trees instead of two. So, he removed one more edge from some of the trees he had.
And so on. Every day, Chef was removing one, not yet removed edge, util he once got a forest, consisting of N singlenode trees.
Chef thinks that the main characteristic of a tree is its' diameter. So he asks you to calculate the product of the diameters in obtained set of trees.
Since the overall product might be quite large, output it modulo 10^{9}+7.
Note
In this problem, we consider the diameter of the tree as the maximum sum of weights of the nodes over all simple paths in this tree.
Input
The first line of the input contains an integer N denoting the number of nodes in the tree T.
The following line contains N spaceseparated integers W_{i}, denoting the weights of the nodes.
Each of the following (N1) lines contain two spaceseparated integers X_{i} Y_{i}.
Each of the following (N1) lines contain a single integer K_{j}, denoting the number of the edge that will be deleted on the j^{th} day.
Output
Output N lines.
On the i^{th} line, output the product of the diameters of all the trees after (i1) days modulo 10^{9}+7. Formally, if i > 1, output the product of the diameters of the obtained trees after deleting the edges K_{1}, K_{2}, ..., K_{i  1}, modulo 10^{9}+7, otherwise output the diameter of the initial tree.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ W_{i} ≤ 10^{4}
 1 ≤ X_{i}, Y_{i} ≤ N
 K is a permutation of the integers from the range [1; N1].
Subtasks
 Subtask #1 (16 points): 1 ≤ N ≤ 100
 Subtask #2 (24 points): 1 ≤ N ≤ 5000
 Subtask #3 (60 points): no additional constraints
Example
Input: 3 1 2 3 1 2 1 3 2 1 Output: 6 9 6
Explanation
The diameter of the initial tree is 6 (node 2 to node 1 to node 3).
After the first day (the deletion of the 2^{nd} edge, i.e. 1 3), we get two trees, both with diameters 3.
After the second day (the deletion of the 1^{st} edge, i.e. 1 2), we get three trees with diameters 1, 2, 3, and their product equals to 6.
Author:  xcwgf666 
Tester:  harshil7924 
Editorial  http://discuss.codechef.com/problems/TREEDIAM 
Tags  lca, ltime39, medium, tree, unionfind, xcwgf666 
Date Added:  6082016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions