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 ≤ 10^{5}, the number of friends (N) and the number of queries.
The next line will contain N integers 0≤ A_{i} ≤ 10^{5}, the team which i^{th} friend supports.
The next N1 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 ≤ 10^{5}), meaning that x^{th} 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
vict_ansh:
20190518 08:44:18
how can we solve this?? 

morass:
20171029 20:37:52
@yogahmad: ^_^ Glad you made it through!


yogahmad:
20171029 17:44:18
@morass


morass:
20171029 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 runtime used) 

yogahmad:
20171026 02:34:22
I think the time limit is too strict. 

morass:
20171024 21:06:31
@yogahmad: O(N^5/3) shall pass :) 

yogahmad:
20171024 16:37:24
what is the expected complexity for this problem? 

morass:
20171008 11:05:13
[Rampage] Blue.Mary: Good day to you, and sorry for inconvenience.


[Rampage] Blue.Mary:
20171008 09:50:44
" 0 ≤ a b ≤ N " actually means " 0 ≤ a b < N and a != b"?

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