Задача A. Дерево

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа ui и vi через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

Задача B. Радиус дерева

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Деревом называется связный неориентированный граф без циклов. Для заданного дерева требуется найти радиус.

Напишите программу, принимающую описание дерева и выводящую радиус дерева.

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа ui vi — номера вершин, которые соединены этим ребром.

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

Выходной файл должен содержать единственное целое число — радиус дерева.

Ограничения

2 ≤ N ≤ 105, 1 ≤ ui, vi ≤ N.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
1
2
3
1 2
1 3
1
3
7
1 4
2 3
2 4
2 5
4 6
4 7
2

Задача C. Расстояние от корня

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

В заданном корневом дереве найдите вершины, максимально удалённые от корня. Расстоянием между вершинами считается количество рёбер в пути.

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

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, , n. Вершина 1 является корнем дерева.

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

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева.

Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии.

В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1
1
1
2
2 3
2
3
1
2
2
1
3

Задача D. Выбор вершин взвешенного дерева

Автор:Тренировки СПбГУ   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Рассмотрим все допустимые множества вершин графа. Для каждого такого множества вычислим сумму чисел, написанных в его вершинах. Какова максимальная из этих сумм?

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

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

В первой строке входного файла записано целое число n  — количество вершин в графе . В следующих n строках задан граф. В i-й из этих строк записаны через пробел два целых числа pi и qi; здесь pi  — номер вершины-предка i-ой вершины, а qi  — число, записанное в этой вершине. Для корня дерева pi = 0; для всех остальных вершин 1 ≤ pi ≤ n.

Гарантируется, что заданный во входном файле граф является деревом.

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

В первой строке выходного файла выведите одно число — максимальную сумму чисел в допустимом множестве.

Ограничения

1 ≤ n ≤ 100

1 ≤ pi ≤ n

|qi| ≤ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
0 1
1 2
1 3
2 4
3 5
10
2
6
5 8
6 0
5 -1
1 1
0 3
1 2
8

Задача E. Простые пути в дереве

Автор:Тренировки СПбГУ   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

На первой строке целое число n. Следующие n1 строка содержат пары чисел от 1 до n  — ребра графа.

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

n1 строка. i-я строка должна содержать целое число  — ответ для i-го ребра.

Ограничения

2 ≤ n ≤ 300000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2
2 3
2 4
5 1
13
8
8
9

0.037s 0.003s 15