Модуль: Динамическое программирование на графах


Задача

1 /7


Бюрократия

Теория Нажмите, чтобы прочитать/скрыть

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

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

Для начала подвесим дерево за какую-нибудь вершину (например за вершину с номером 1).
Будем рассматривать два типа путей:
1) Вертикальные пути - один из концов пути является предком второго конца.
2) Горизонтальные пути - ни один из концов пути не является предком второго.
Любой путь в дереве относится к одному из этих типов.

У каждого горизонтального пути есть высшая точка, которая является наименьшим общим предком двух концов этого пути. Для вертикального пути высшей точкой является просто конец-предок.
Чтобы рассмотреть все возможные пути будем перебирать высшие точки путей. Допустим мы зафиксировали некоторую вершину. Если это высшая точка некоторого вертикального пути, то второй конец - это вершина, которая лежит где-то в поддереве зафиксированной вершины. Если же это высшая точка горизонтального пути, то первый конец пути лежит в поддереве левого ребенка, а другой конец лежит в поддереве правого ребенка (а иначе вершина v на самом деле не является высшей точкой). Будем пользоваться этим, чтобы вычислять оптимальные пути.

Для решения воспользуемся динамическим программированием: dp[v] - значение максимального веса вертикального пути с высшей точкой в вершине v.
Подсчет dp[v] - есть три способа построить оптимальный вертикальный путь с высшей точкой в вершине v:
1) Путь, который состоит только из вершины v. Тогда вес равен просто весу вершины v. Это можно использовать как начальное значение динамики.
2) Взять оптимальный вертикальный путь с высшей точкой в левом ребенке и продлить его вершиной v. Значение такого пути равно dp[left] + w(v).
3) Взять оптимальный вертикальный путь с высшей точкой в правом ребенке и продлить его вершиной v. Значение такого пути равно dp[right] + w(v).

Если взять максимальное значение dp[v], то узнаем максимальный вес вертикальных путей.
Осталось учесть горизонтальные пути. Их также можно считать при помощи dp. Зафиксировав вершину v как высшую точку горизонтальных путей, нужно просто взять значение dp[left] + w(v) + dp[right], так как в высшей точке просто соединяются два вертикальных пути из разных поддеревьев. Учитывая эти значения при всех v, мы можем определить максимальный вес среди всех путей. 

Реализовать это все можно через обход дерева в глубину. Подробнее в коде:
  
// Структура для хранения бинарного дерева
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

// глобальный ответ - значение максимального пути
int res;

// dp[v] - значение максимального пути, 
// у которого высшая вершина v, а нижняя где-то в поддереве вершины v

// вместо того, чтобы хранить массив dp
// будем просто возвращать его в качестве значения рекурсии (обхода в глубину)
int calc(TreeNode* v) {

	// vert - вертикальный путь из вершины v, фактически - значение dp[v]
	// начальное значение - значение в вершине v, то есть путь только из вершины v
	int vert = v->val;

	// hor - горизонтальный путь, у котого высшая точка (lca) это вершина v
	// инициализируем значением в вершине v
	int hor = v->val;

	// если левый ребенок существует
	if (v->left != nullptr) {
		int d = calc(v->left); // посчитали значение динамики у левого ребенка
		vert = max(vert, d + v->val); // обновляем вертикальный путь как продолжение пути левого ребенка
		hor += d; // добавляем левую ветвь горизонтального пути
	}

	// если правый ребенок существует
	if (v->right != nullptr) {
		int d = calc(v->right); // посчитали значение динамики у левого ребенка
		vert = max(vert, d + v->val); // обновляем вертикальный путь как продолжение пути правого ребенка
		hor += d; // добавляем правую ветвь горизонтального пути
	}

	// обновляем глобальный ответ через вертикальный путь с высшей точкой в v
	res = max(res, vert);

	// обновляем глобальный ответ через горизонтальный путь с высшей точкой (lca) в v
	res = max(res, hor);

	// возвращаем значение динамики вершины v
	return vert;
}

int maxPathSum(TreeNode* root) {
	// изначальное максимальное значение равно нулю - пустой путь, не содержащий вершин
	res = 0;

	// запускаем обход в глубину
	calc(root);

	// теперь у res актуальное значение
	return res;
}
 

Задача

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, которые пронумерованы числами от 1 до N, причем сам Мирко имеет номер 1. У всех работников, кроме Мирко, есть начальник. Начальник может иметь несколько подчиненных, но не более одного своего начальника.

Когда Мирко получает задание от инвесторов, он передает его своему подчиненному с наименьшим номером. Этот подчиненный также передает его своему подчиненному с наименьшим номером, и так далее, пока задание не перейдет несчастливому работнику без подчиненных, который должен его выполнить.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 монеты, и так далее. Потом тот, кто на самом деле сделал работу, осознает, насколько эта капиталистическая система несправедлива, и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации.

Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.

Входные данные:
Первая строка содержит одно натуральное число N (1 ≤ N ≤ 2·105) — число сотрудников компании. Следующая строка содержит N-1 чисел a2, a3, ... an (1 ≤ ai < i), ai — номер начальника i-го сотрудника.

Выходные данные:
Выведите N чисел, i-е число должно означать, сколько монет получил i-й сотрудник.

Примеры:
 
Входные Данные Выходные данные
3
1 1		 5 1 1
5
1 2 2 4		 13 8 1 3 1

Пояснения:

Далее приведено описание ко второму примеру.

Мирко отдает первое задание работнику 2, который передает его работнику 3, который выполняет задание. Таким образом, работник 3 получает одну монету, работник 2 — две монеты, а работник 1, сам Мирко, — три монеты. После этого работник 3 увольняется.
Мирко отдает второе задание работнику 2, который передает его работнику 4, который тут же передает задание работнику 5, который выполняет задание. После этого работник 5 получает одну монету, работник 4 — две монеты, работник 2 — три монеты, а Мирко — четыре монеты. Работник 5 увольняется.
После выполнения третьего задания работник 4 получает одну монету, работник 2 — две монеты, а Мирко — три монеты, после чего работник 4 увольняется.
После выполнения четвертого задания работник 2 получает одну монету, а Мирко — две монеты, после чего второй работник увольняется.
Наконец, пятое задание выполняет сам Мирко, получая за это одну монету, после чего процесс прекращается.

Суммарно Мирко получил 13 монет, работник 2 — 8 монет, работник 4 — 3 монеты, а работники 3 и 5 — одну монету.

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

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