Олимпиадный тренинг

Задача . Balanced Trees


Задача

Темы: Деревья

Ферма Джона - гигантское дерево из N пастбищ (1 <= N <= 40,000), каждое из которых помечено символом ( или символом ).
Например:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' | | ')' '('--')'--')'--')'--'('
Поскольку ферма дерево - то некоторые пары пастбищ соединены дорожками, так что существует уникальный путь между любыми двумя парами пастбищ. Некоторые из этих путей представляют сбалансированные строки скобок. Теперь ФД хочет узнать какова максимальная глубина вложенности среди всех сбалансированных строк представляющих эти пути.
Максимальной глубиной вложенности сбалансированной строки скобок называется максимальное превышение количества левых скобок над правыми среди всех префиксов этой строки. Например, для строки ()()() максимальная глубина вложенности - 1, а для строки ((()))() максимальная глубина вложенности - 3:
((()))() 12321010
Для примера фермы, представленного выше "наиглубокая" строка есть ((())), ее глубина равна 3, а строка получается по пути из A в B:
'('--'('--')'--'('--')' | | ')' ')'--'('--'(' < A | | ')' '('--')'--')'--')'--'(' ^C ^B
Заметим, что она отличается от самой длинной сбалансированной строки (())(()), которая начинается в A, заканчивается в C и имеет длину 8.
Ваша задача - вывести максимальную глубину вложенности среди путей на данном дереве.
PROBLEM NAME: btree
Формат входных данных
* Строка 1: Одно целое число N, количество вершин в дереве.
* Строки 2..N: Строка i+1: Одно целое число p_(i+1) (1 <= p_(i+1) <= i), означающее, что существует ребро между вершинами I+1 и P_(I+1) в этом дереве.
* Строки N+1..2N: Строка N+i: Или ( или ), метка вершины i.
Формат выходных данных
* Строка 1: Одно целое число - максимальная глубина вложенности среди всех сбалансированных путей
Примеры
№Входные данныеВыходные данные
1 
15
1
2
1
4
4
6
7
5
9
9
11
12
13
14
(
)
)
(
)
)
(
)
(
(
(
)
)
)
(
 
3
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет