题意: 给一个树加最少的边, 使得 1 到所有点的距离小于等于 2.
解题思路: 分析样例 3 可以看出, 如果一个点到 1 的距离大于 2, 那么建立 1 到该点的父亲节点的边将比直接与该点建边更优. 官方题解的做法是把所有与 1 距离大于 2 的点放到大顶堆里维护, 每次取出最远的点, 染色与该点父节点以及与父节点相接的所有点. 也就是相当于与父节点建边, 距离为 1, 与父节点的子节点的距离就为 2 了, 于是把这些点弹出. 从大佬博客中学到一个很妙的写法, 是用 dfs 实现这个思路, 具体看代码.
附 ac 代码:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 2e5 + 10;
- int dis[maxn];
- vector<int>nu[maxn];
- int ans = 0;
- void dfs(int now, int pre, int cnt)
- {
- dis[now] = cnt;
- int flag = 0;
- for(int y : nu[now])
- {
- // printf("%d\n", y);
- if(y == pre) continue;
- dfs(y, now, cnt + 1);
- if(dis[y]> 2)
- {
- flag = 1;
- dis[now] = 1;
- dis[pre] = 2;
- }
- }
- ans += flag;
- }
- int main()
- {
- int n;
- int u, v;
- scanf("%d", &n);
- for(int i = 1; i < n; ++i)
- {
- scanf("%d %d", &u, &v);
- nu[u].push_back(v);
- nu[v].push_back(u);
- }
- dfs(1, 1, 0);
- printf("%d\n", ans);
- }
- View Code
来源: http://www.bubuko.com/infodetail-2757064.html