題目鏈接

題意

給你一棵樹，最多加幾條邊，使點1到所有的點的最大距離不超過2

AC

• 貪心
• 從距離最遠的點開始，找到他的父節點，然后把父節點相連的點刪去，這樣最好的情況可以刪除三層點

遍歷樹的時候有兩種方法：

// bfs #include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 200005 using namespace std;vector<int> g[N]; int pre[N], dis[N];// bfs遍歷整棵樹 struct point{int num, dis; }; bool vis[N]; void bfs(int x) {queue<point> que;que.push((point){x, 0});vis[x] = true;pre[x] = 0;while (!que.empty()) {point f = que.front();que.pop();vector<int>::iterator it;for (it = g[f.num].begin(); it != g[f.num].end(); ++it) {if (vis[*it]) continue;vis[*it] = true;pre[*it] = f.num;dis[*it] = f.dis + 1;que.push((point){*it, dis[*it]});}} }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n - 1; ++i) {int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}// bfs 遍歷整棵樹，得到每個點到 1 的距離和他們的pre memset(vis, false, sizeof(vis));bfs(1); // 一開始用vector 超時了，主要是find的函數的差別 set<pair<int, int> > st;for (int i = 1; i <= n; ++i) {if (dis[i] > 2) {// 存負值， set是升序 st.insert(make_pair(-dis[i], i));}} int ans = 0;set<pair<int,int> >::iterator tar;vector<int>::iterator it;while (!st.empty()) {// 選取第一個 int v = st.begin()->second;// 找到他的父節點，將線連到父節點 v = pre[v];ans++;// 如果父節點在set中就刪除，這里 WA 一次 tar = st.find(make_pair(-dis[v], v));if (tar != st.end()) st.erase(tar);// 遍歷父節點連接的點，如果在set中就刪除 for (it = g[v].begin(); it != g[v].end(); ++it) {tar = st.find(make_pair(-dis[*it], *it));if (tar != st.end()) st.erase(tar);} }printf("%d\n", ans);for (int i = 1; i <= n; ++i) {g[i].clear();}st.clear();} return 0; } // dfs #include <iostream> #include <cmath> #include <map> #include <vector> #include <set> #include <cstring> #include <queue> #include <algorithm> #define ll long long #define ull unsigned long long #define N 200005 using namespace std;vector<int> g[N]; int pre[N], dis[N];// dfs遍歷整棵樹 void dfs(int x, int pr, int dist) {dis[x] = dist;pre[x] = pr;vector<int>::iterator it;for (it = g[x].begin(); it != g[x].end(); ++it) {// 往下遍歷 if (*it == pr) continue;dfs(*it, x, dist + 1);} }int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endif int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n - 1; ++i) {int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0, 0); set<pair<int, int> > st;for (int i = 1; i <= n; ++i) {if (dis[i] > 2) {st.insert(make_pair(-dis[i], i));}} int ans = 0;while (!st.empty()) {int v = st.begin()->second;v = pre[v];ans++;set<pair<int,int> >::iterator tar;tar = st.find(make_pair(-dis[v], v));if (tar != st.end()) st.erase(tar);vector<int>::iterator it;for (it = g[v].begin(); it != g[v].end(); ++it) {tar = st.find(make_pair(-dis[*it], *it));if (tar != st.end()) st.erase(tar);} }printf("%d\n", ans);for (int i = 1; i <= n; ++i) {g[i].clear();}st.clear();}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #506 (Div. 3) - E. Tree with Small Distances的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。