Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Change Queries

By subhashis_cse · Limits 1s, 512 MB

Today is a very special day for Rubel. Recently he got a job in a software company. Now today is the first day of his job life. One of the deparment of the company is “CREATIVE”. And he has been assigned for this department and also assigned a mentor named “Anindo”.

Now Anindo gives him n works that are numbered 1 to n and each of works have some cost. Anindo told him that there are some jobs that are dependent on other jobs and there may be some jobs that are not dependent on others.

Now you are given the cost of all works and the dependency of works.

And there have some queries also . Your task is to process following types of queries:

1. Change the cost of the work no W to C
2. Calculate the sum of cost of all works (include W) that are dependent on the work W.

If a is depends on b, b depends on c then it is said that a is depends on c also.

Here n-1 works are dependent on exactly one another work.

Input

The first input line contains two integers n and q: the number of works and queries. The works are numbered 1,2,…,n ( 1<=n,q<=2 * 10^5 ) .

The next line has n integers C1,C2,………,Cn: the cost of each work. ( 1 <= Ci <= 10^9 )

Then there are n−1 lines describing the dependencies. Each line contans two integers u and v: that means v is dependent on u but u is not dependent on v. (1 <= u,v <= n)

Finally, there are q lines describing the queries. Each query is either of the form “1 W C” or “2 W”. (1<=W<=n && 1<=C<=10^9)

Output

Print the answer to each query of type 2.

Sample

InputOutput
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

8
10


Statistics

67% Solution Ratio

moshiur_cse15Earliest, 10M ago

Deshi_TouristFastest, 0.1s

robiulRonyLightest, 18 MB

TasdidShortest, 1478B