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 gained 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
bocha_123:
2020-11-09 16:44:20
not able to understand the problem |
|
vict_ansh:
2019-05-18 08:44:18
how can we solve this?? |
|
morass:
2017-10-29 20:37:52
@yogahmad: ^_^ Glad you made it through!
|
|
yogahmad:
2017-10-29 17:44:18
@morass
|
|
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.
|
|
[Rampage] Blue.Mary:
2017-10-08 09:50:44
" 0 ≤ a b ≤ N " actually means " 0 ≤ a b < N and a != b"?
|
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 |