Печери та тунелі#5285
Після посадки на поверхню Марса вчені виявили дивну систему печер, з’єднаних тунелями. Вони почали досліджувати її за допомогою дистанційно керованих роботів. Виявилось, що між кожною парою печер існує рівно один маршрут. Однак дослідники зіткнулися з особливою проблемою: іноді у печерах відбуваються слабкі вибухи. Вони призводять до викиду радіоактивних ізотопів і підвищення рівня радіації у печері. На жаль, роботи погано переносять радіацію. Проте для проведення досліджень їм доводиться переміщатися з однієї печери до іншої. Тому вчені встановили у кожній печері сенсори для моніторингу рівня радіації. Тепер при кожному переміщенні робота вчені хочуть знати максимальний рівень радіації, з яким робот зіткнеться під час свого переміщення.
Тому вони попросили вас написати програму, яка розв’яже цю задачу.
Перший рядок містить одне ціле число (1 \leq N \leq 100\,000) — кількість печер. Наступні N-1 рядків описують тунелі. Кожний з них містить два цілі числа a_i та b_i (1 \leq a_i, b_i \leq N), які визначають номери печер, з'єднаних відповідним тунелем. Наступний рядок містить ціле число (1 \leq Q \leq 100\,000), що позначає кількість запитів. Далі йде рядків із запитами у форматі "C U V", де — символ 'I' або 'G', що вказує тип запиту (лапки лише для ясності).
Якщо тип запиту — 'I', рівень радіації у -й печері (1 \leq U \leq N) збільшується на (0 \leq V \leq 10\,000). Якщо тип запиту — 'G', ваша програма має вивести максимальний рівень радіації на шляху між печерами з номерами та (1 \leq U, V \leq N) після всіх попередніх збільшень ('I'-запити). Початково у всіх печерах рівень радіації дорівнює і ніколи не зменшується з часом (оскільки період піврозпаду ізотопів набагато більший за час спостережень).
Для кожного запиту 'G' виведіть єдине число — максимальний рівень радіації на відповідному шляху.
Приклад 1