[HackerEarth] Bear recently studied the depth first traversal of a Tree in his Data Structure class. He learnt the following algorithm for doing a dfs on a tree. - P14963

P14963 [HackerEarth] Bear recently studied the depth first traversal of a Tree in his Data Structure class. He learnt the following algorithm for doing a dfs on a tree.

普及

题目描述

Bear recently studied the depth first traversal of a Tree in his Data Structure class. He learnt the following algorithm for doing a dfs on a tree.

void dfs(int v,int p){
vis[v] = 1;
for(int i=0;i<G[v].size();++i){
if(G[v][i]!=p)
dfs(G[v][i],v);
}
}

Now he was given an array A, Tree G as an adjacency list and Q queries to answer on the following modified algorithm as an homework.

void dfs(int v,int p){
vis[v] += 1;
for(int j=1;j ≤ A[v];++j){
for(int i=0;i<G[v].size();++i){
if(G[v][i]!=p)
dfs(G[v][i],v);
}
}
}

The Q queries can be of the following two types :
$1\space v\space x$ : Update A[v] = x. Note that updates are permanent.
$2\space v$ : Initialize $vis[u] = 0 \space \forall \space u$ ∈ [1,N]. Run the above algorithm with call dfs(1,-1). Compute the sum $\large\displaystyle \sum_{u$ ∈ $Subtree\space$ of$\space v}^v vis[u].$ As the result may be quite large print it $mod\space 10^9+7$

INPUT
The first line contains two integers N and Q, the number of vertices in the tree and the number of queries respectively.
Next N-1 lines contains the undirected edges of the tree.
The next lines contains N integers denoting the elements of array A.
Following Q lines describe the queries.

OUTPUT
For each query of type 2, print the required result $mod\space 10^9+7$.

CONSTRAINT
1 ≤ N, Q ≤ 10^5
1 ≤ $A[v],\space x$ ≤ 10^9
1 ≤ v ≤ N

SAMPLE INPUT
4 9
1 2
2 3
3 4
1 1 1 1
2 1
2 2
2 3
2 4
1 3 100
2 1
2 2
2 3
2 4

SAMPLE OUTPUT
4
3
2
1
103
102
101
100

输入格式

见题面

输出格式

见题面

样例输入

10
1
2
7
4
3
6
1
1
4
733 36 947 339 687 854 295 29 11 
8
1 166
6
5
7
8 807
7
4 353
5 418
8 725

样例输出

题目信息

时间限制	2000 ms
内存限制	256 MB
难度	普及
提交数	0
通过数	0
通过率	0.0%

登录后 AI 解题查看题解登录后提交