厦门网站建设方案咨询,中国建筑网上测评,编程课程培训机构排名,推广普通话演讲稿Linova and Kingdom—CF1336A 参考文章
思路 1 1 1 号节点为根节点。很容易想到#xff0c;工业城市在树的下边#xff0c;旅游城市在树的上边。具体来说#xff0c;如果节点 u u u 是工业城市#xff0c;那么它的子树的所有节点一定都是工业城市#xff1b;如果节点 u…Linova and Kingdom—CF1336A 参考文章
思路 1 1 1 号节点为根节点。很容易想到工业城市在树的下边旅游城市在树的上边。具体来说如果节点 u u u 是工业城市那么它的子树的所有节点一定都是工业城市如果节点 u u u 是旅游城市那么它到根节点的路径上的所有城市都是旅游城市。
我们先把所有城市认定为工业城市然后在与工业城市直接相连的旅游城市中选出“将其变为工业城市提供的贡献值”最大的城市并将其变为工业城市。
城市的贡献的计算方法当前点的子树的节点数 - (当前点的深度 - 1)。
可以利用用优先队列来选出最佳的城市然后再将新产生的满足条件的城市压入队列。
由于我们选出的“贡献点最大的城市”的前提是这个点设为 w w w 点的子树上所有点都是工业城市并且与根节点路径上的所有点都是旅游城市。那么如果后边的操作把 w w w 点的子节点给变成了旅游城市那么不就不满足这个条件了吗
请认真考虑我们是如何计算计算一个边界处的旅游城市如果变为工业城市后可以提供的贡献的当前点的子树的节点数 - (当前点的深度 - 1)。 w w w 的贡献是相对于“ w w w 点及 w w w 点到根节点路径上都是旅游城市的条件”也就是这种计算贡献的方法考虑了上一个状态并非独立计算某一个点的贡献。 C o d e Code Code
#include bits/stdc.h
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII pairint, int;
using i128 __int128;
const int N 2e5 10;int n, k;
int contri[N];void solve() {cin n k;vectorvectorint g(n 1);for (int i 1; i n - 1; i ) {int a, b; cin a b;g[a].push_back(b);g[b].push_back(a);}// 计算深度和子树中节点数量vectorint deep(n 1, -1), son_num(n 1);auto dfs [] (auto dfs, int u) -int {int sum 1;for (auto v : g[u]) {if (deep[v] -1) {deep[v] deep[u] 1;sum dfs(dfs, v);}}son_num[u] sum;return sum;};deep[1] 1;dfs(dfs, 1);// 计算每个点的贡献for (int i 1; i n; i ) {son_num[i] --;contri[i] son_num[i] - (deep[i] - 1);}int res 0;k n - k;vectorint st(n 1, 0); // 标记是否为旅游城市/已经来过priority_queuePII, vectorPII q; // [贡献节点] 降序优先队列q.emplace(contri[1], 1);while (not q.empty() k --) {auto [f, s] q.top(); q.pop();st[s] 1;res f;for (auto v : g[s]) {if (not st[v]) {q.emplace(contri[v], v);}}}cout ;cout res \n;
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T 1;
// cin T; cin.get();while (T --) solve();return 0;
}
