На этот раз вам нужно помочь группе ученых-исследователей на одном острове в Тихом Океане. Они изучают культуру древних племен, живших на этом острове много лет назад.
Всего было раскопано n деревень. Некоторые пары деревень были соединены дорогами. По дорогам можно было двигаться в обоих направлениях. Всего было ровно n - 1 дорог, и из любой деревни можно было добраться в любую другую.
Племена были неспокойны и часто воевали. В результате войн некоторые деревни полностью уничтожались. В более спокойные годы некоторые из деревень возрождались заново.
В каждый момент времени использовались только те дороги, которые принадлежали какому-либо кратчайшему пути между двумя существующими в данный момент деревнями. Другими словами, использовалось наименьшее подмножество дорог так, чтобы из любой существующей деревни можно было добраться до любой другой существующей. Обратите внимание, что за всю историю острова существовало ровно n - 1 дорог, найденных исследователями, а других дорог никогда не было.
Исследователи полагают, что наблюдения за суммарной длиной используемых дорог в разные моменты времени помогут им лучше понять культуру племен и ответить на ряд исторических вопросов.
Вам будет предоставлена вся история существования племен. Ваша задача — определить суммарную длину используемых дорог в некоторые из моментов времени.
Выходные данные
На каждый запрос типа «?» выведите суммарную длину используемых дорог в отдельной строке. Ответы за запросы должны быть выведены в том порядке, в котором запросы перечислены во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?
|
5
14
17
10
|