ADAFTBLL - Ada and Football


Ada the Ladybug has many friends who live on a tree. Each of them is fan of a football team. Ada sometime go on a trip from one friend to another. If she meets a friend she tells him/her about all previously visited friends who are fans of the same team. The visited friend will gain +1 happiness for each friend Ada told him/her about.

Ada is wondering (for each trip) what will be the total gaines happiness.

Also note that sometime a friend changes his/her mind and start to support different team.

Input

The first line two integers 1 ≤ N Q ≤ 105, the number of friends (N) and the number of queries.

The next line will contain N integers 0≤ Ai ≤ 105, the team which ith friend supports.

The next N-1 lines will contain two integers 0 ≤ a, b < N, the friends which will be connected by a branch (edge).

The next Q lines will be of two kinds:

1 x y (0 ≤ x < N, 0 ≤ y ≤ 105), meaning that xth friend will start supporting team y (instead of the old one).

2 a b (0 ≤ a, b < N), meaning that Ada will travel from friend a to friend b and wants to know the happiness.

Output

For each query of second kind, output the gained happiness.

Example Input

7 8
0 0 1 2 1 1 2
0 1
1 5
1 2
2 4
2 3
3 6
2 4 5
2 0 6
2 1 3
1 1 2
1 2 2
2 4 5
2 0 6
2 1 3

Example Output

3
2
0
2
6
3

hide comments
morass: 2017-10-29 20:37:52

@yogahmad: ^_^ Glad you made it through!
PS: Now you have more than 2s reserve ^_^

yogahmad: 2017-10-29 17:44:18

@morass
Sorry it was my stupid mistakes.
Thanks for the great problem. :)

morass: 2017-10-29 01:18:35

@yogahmad: The three accepted solutions has reserve from 1.2 to 1.6 on worst case, whch I consider enough to pass (it is around half of the run-time used)

yogahmad: 2017-10-26 02:34:22

I think the time limit is too strict.

morass: 2017-10-24 21:06:31

@yogahmad: O(N^5/3) shall pass :)

yogahmad: 2017-10-24 16:37:24

what is the expected complexity for this problem?

morass: 2017-10-08 11:05:13

[Rampage] Blue.Mary: Good day to you, and sorry for inconvenience.

a) Yes, you are right, thank you

b) Seems to be so, thank you [Please try to resubmit and again, sorry for inconvenience]

Last edit: 2017-10-08 11:13:36
[Rampage] Blue.Mary: 2017-10-08 09:50:44

" 0 ≤ a b ≤ N " actually means " 0 ≤ a b < N and a != b"?
"1 x y (0 ≤ x ≤ N ..." actually means "1 x y (0 ≤ x < N ..."?

(Btw, are you sure all your test cases are right?)

Last edit: 2017-10-08 10:15:39

Added by:Morass
Date:2017-10-08
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01