#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <Bits.h>
using namespace std;
vector<vector<int>> graph;
vector<bool> visited;
int check(int currentCity, int k) {
int childrenSum = 0;
visited[currentCity] = true;
for (int i = 0; i < graph[currentCity].size(); i++) {
if (!visited[i]) {
childrenSum += check(graph[currentCity][i], k);
}
}
int numberOfChildren = graph[currentCity].size() - 1;
if (currentCity == 0) numberOfChildren++;
return max(0, numberOfChildren + childrenSum - k);
}
int main() {
int numberOfTowns;
cin >> numberOfTowns;
visited.resize(numberOfTowns);
graph.resize(numberOfTowns);
for (int i = 0; i < numberOfTowns - 1; i++) {
int a, b;
cin >> a >> b;
a--;
b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
int start = 1;
int end = numberOfTowns;
int currentK;
while (start != end) {
visited.resize(numberOfTowns, false);
currentK = (start + end) / 2;
if (!check(0, currentK)) {
end = currentK;
}
else {
start = currentK + 1;
}
}
cout << currentK << endl;
system("pause");
return 0;
}
Compilation message
luk.cpp:8:10: fatal error: Bits.h: No such file or directory
#include <Bits.h>
^~~~~~~~
compilation terminated.
