18505번 - Tree of Charge 다국어

There is a rooted tree. Each vertex contains some non-negative amount of charge c_v. You have to process three kinds of queries:

• Move the charge up: all vertices simultaneously transfer all their charge to their direct parent. The charge from the root is not transferred anywhere. That is, if vertex v had children u₁, . . . , u_k, then its new charge becomes c_u1 + . . . + c_uk for a non-root vertex v, or c_u1 + . . . + c_uk + c_v if v is the root.
• Move the charge down: all vertices simultaneously transfer all their charge to their children in equal proportions. That is, if vertex v had children u₁, . . ., u_k, then the new charge of each u_i becomes c_v/k.
  There is a virtual line tree of sufficient length attached to each leaf. That is, if the charge is moved down from the leaf and then moved up the same number of times, then the leaf retains its original charge.
• Add charge to a vertex: add a certain amount of charge to a certain vertex.

At the end, you should print the value of charge in each vertex.

In the first line of input there is a single integer n, the number of vertices in the tree (2 ≤ n ≤ 500 000).

The next line contains n integers c_i, i-th of them denoting the initial charge of the tree (0 ≤ c_i < 10⁹ + 7).

Each of the next n − 1 lines contains two integers u_i and v_i denoting the edge between vertices u_i and v_i (1 ≤ u_i, v_i ≤ n).

Next line contain a single integer q, the number of queries (0 ≤ q ≤ 500 000). Then q lines follow with the description of queries. “Move up” query is denoted with a character “ˆ”. “Move down” query is denoted with a character “v”. “Add charge” query is denoted with a character “+” followed by two integers v_i and x_i, meaning that you should add charge x_i to vertex v_i (1 ≤ v_i ≤ n, 0 ≤ x_i < 10⁹ + 7).

It is guaranteed that the graph in the input is a tree.

Print n numbers, i-th of them being the final charge of vertex i modulo 10⁹ + 7.

Formally, let the charge be p/q. Then you should print a unique number x, 0 ≤ x < 10⁹ + 7, such that p ≡ x · q mod 10⁹ + 7.