Квіти
Обмеження: 2 сек., 256 МіБ
Джон і Брюс часто відвідують ліс неподалік свого будинку. У лісі є n прекрасних полян і n−1 двостороння стежка. Кожна стежина з’єднує дві поляни. З кожної поляни стежками можна добратися до будь-якої іншої. Тому є рівно один простий шлях (тобто шлях, який складається з різних стежок) від однієї поляни до іншої.
Джон: Брюсе, ці квіти для тебе!
Брюс: Чудово, вони прекрасні! Але чому їх тільки чотири?
Хлопці відвідуватимуть ліс упродовж m днів поспіль. Перед першим днем на i-й поляні росте fi дуже гарних квітів. На початку кожного дня на кожній поляні з’являтиметься по одній додатковій квітці.
Після цього Джон і Брюс або зірвуть усі квіти на поляні, або порахують кількість квіток на простому шляху між двома полянами включно.
Вхідні дані
У першому рядку задано два цілі числа n і m.
Наступний рядок містить n цілих чисел fi.
Кожен із наступних n−1 рядків містить цілі числа ai та bi — поляни, з’єднані i-ою стежкою.
Кожен із наступних m рядків
починається з одного символа (P
чи C
). Якщо це
P
, то після нього слідує ціле число gi — це значить, що в i-ий день хлопці зірвуть усі квіти на
поляні gi. Інакше після символа
C
слідують два цілі числа ui та vi. У цьому разі Джон і Брюс порахують
кількість квітів на простому шляху між полянами ui та vi включно.
Вихідні дані
Для кожного підрахунку виведіть рядок, що містить обчислену кількість квітів.
Обмеження
1≤n,m≤105,
0≤fi≤109,
1≤ai,bi,gi,ui,vi≤n.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 3 4 7 1 2 C 1 2 P 2 C 1 2 | 13 8 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
1 1 100 C 1 1 | 101 |