Решение задачи Linova и королевство с Codeforces

Без пояснения   Просмотров: 60


Написание легких романов является очень важной частью жизни Linova. Прошлой ночью ей приснилось сказочное королевство. Linova написала легкий роман про это королевство, как только проснулась. Конечно, она стала его королевой.



Всего есть n городов и n−1 двусторонняя дорога, соединяющая некоторые пары городов королевства. Из любого города вы можете попасть в любой другой город, пройдя по некоторым дорогам. Города пронумерованы от 1 до n и город 1 является столицей королевства. Таким образом, структура королевства является деревом.

Как королева, Linova планирует выбрать ровно k городов для развития индустрии, тогда как в остальных городах будет развиваться туризм. Столица также может быть как индустриальным, так и туристическим городом.

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

Путешествие по туристическим городам очень приятно. Для каждого посланника, его уровень счастья равен количеству туристических городов на его пути.

Для того, чтобы люди любили королеву, Linova хочет выбрать k городов так, чтобы максимизировать сумму уровней счастья всех посланников. Можете ли вы посчитать максимальную возможную сумму для нее?

Код

#include <bits/stdc++.h>
using namespace std;

const int M = 2e5 + 100;
vector<int> e[M], v;

int dfs(int u, int p, int dep) {
	int son = 1;
	for (int v : e[u]) {
		if (v != p) {
			son += dfs(v, u, dep + 1);
		}
	}
	v.push_back(dep - son + 1);
	return son;
}

int main() {
	int n, k; cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0, 0);
	sort(v.rbegin(), v.rend());
	cout << accumulate(v.begin(), v.begin() + k, 0LL);
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться