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

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

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

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

7
1 4
2 3
2 4
2 5
4 6
4 7

2

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10⁵

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

3
1
1

1
2
2 3

3
1
2

2
1
3

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100

1 ≤ p_i ≤ n

|q_i| ≤ 10⁴

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

5
0 1
1 2
1 3
2 4
3 5

10

6
5 8
6 0
5 -1
1 1
0 3
1 2

8

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

Условие

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

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

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

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

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

Ограничения

2 ≤ n ≤ 300000

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

5
1 2
2 3
2 4
5 1

13
8
8
9