0380. Яблочное дерево

Валера очень любит есть яблоки и, на его счастье, около дома растет большая яблоня. Валера высокий, но яблоня росла на каком-то удивительном удобрении и выросла огромной, поэтому Валера не всегда может дотянуться до яблока. В один прекрасный день ему надоела эта несправедливость, и он решил написать программу, определяющую, какое яблоко расположено ближе всех к земле.

Яблоня представляет собой набор узлов, соединенных ветками. Из каждого узла либо растут ветки (одна или несколько), либо в этом узле находится яблоко. Развитие яблони начиналось из корневого узла. Узлы яблони пронумерованы числами от 1 до N таким образом, что корень имеет номер 1. Будем считать, что высота, на которой растет яблоко, равна расстоянию (измеренному в количестве веток) от узла, на котором растет это яблоко, до корневого узла.

Всё было бы просто, но яблоня – живой организм, и с течением времени ее структура меняется: появляются новые ветки, отваливаются старые узлы (вместе со всеми ветками и узлами, которые на них держались). Валеру постоянно интересует информация о самом нижнем яблоке, поэтому он хочет получать её после каждого изменения в структуре яблони.

Формат входного файла

В первой строке ввода содержится число узлов яблони N (1 ≤ N ≤ 1,5 *10⁵). В следующих N-1 строках содержится описание веток яблони. Каждая ветка описывается двумя целыми числами u_i, v_i, обозначающими номера узлов, которые она соединяет (1 ≤ i < N, 1 ≤ u_i, v_i ≤ N). Гарантируется, что ветки не образуют циклов, а любой узел соединен (напрямую или через другие узлы) ветками с корнем дерева.

В следующей строке содержится целое число T – число событий в <<жизни>> яблони (1 ≤ T ≤ 1,5 *10⁵). Далее идет T строк с описанием событий:

• 1 v u – в узле v выросла новая ветка. Узлу, в котором она заканчивается (а это получается новый узел) присваивается номер u. В новом узле u сразу же вырастает яблоко. Если при этом в узле v было яблоко, то оно упало и больше никого не интересует.
• 2 v – узел v отделяется от яблони. Вместе с узлом v отделяется и все, что непосредственно или косвенно за него держалось. Если в узле, за который держался узел v, не осталось веток (кроме идущей к корню), то там вырастает яблоко.

Гарантируется, что все события корректны, то есть узел с номером v есть в дереве, узла с номером u нет в дереве, а корень дерева никогда не будет отделен. Все числа положительны и не превосходят 1,5 *10⁵.

Обратите внимание, что если какой-то узел оказывается отделен от дерева, то его номер может быть потом использован для обозначения нового узла.

Формат выходного файла

После каждого события необходимо вывести в отдельной строке единственное число – номер наиболее близкого к корню узла, в котором есть яблоко. Если ответов несколько, то можно вывести любой.

Пример:

Source: Petrozavodsk state university championship. October 2014.

Discuss       Submit a solution



Printable version