https://www.spoj.com/problems/ADAFTBLL/
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.