题目链接
题目意思：给一个以\(1\)为根，\(n-1\)条双向边的树形结构，让我们选出\(k\)个节点作为出发点前往根节点\(1\)，算出每一个出发点到根节点的路径上有多少个非出发点的节点数的总和。
思路：如果我们选\(u\)节点作为非出发点的话，\(u\)的子树都会加上\(u\)这个节点的贡献\(1\)，总共\(siz_u-1\)，如果选择\(u\)作为出发点的话，只有\(u\)节点会得到\(dep_u - 1\)的贡献，那么就是选这个节点作为非出发点会比选择作为出发点多得到\(siz_u-dep_u\),那么按照从大到小的顺序将所有节点的\(siz_u-dep_u\)列出来，取前\(n-k\)个节点作为非出发点就可以了。
int n, k;
std::cin >> n >> k;
std::vector<int> adj[n + 1];
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<int> res;
std::vector<int> siz(n + 1), dep(n + 1);
std::function<void(int, int, int)> dfs = [&](int u, int fa, int depth) -> void {
siz[u] = 1, dep[u] = depth;
for (auto& v : adj[u]) {
if (v == fa) continue;
dfs(v, u, depth + 1);
siz[u] += siz[v];
}
res.push_back(siz[u] - dep[u]);
};
dfs(1, 0, 1);
std::sort(res.begin(), res.end(), std::greater<int>());
i64 ans = 0;
for (int i = 0; i < n - k; i++) {
ans += res[i];
}
std::cout << ans << "\n";