[Codeforces1029E] Tree with Small Distances (贪心)

发表于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1029/problem/E

给你一棵树，让你从根节点1向其他点上加边，最少加多少边可以让根节点到所有节点的距离≤2。

考虑贪心，假如一个点n到根节点的距离＞2，显然直接连着两个点不如连这个点的父亲和根来的合算。于是我们贪心地连距离最远的点的父亲，并且更新距离可以了。

先dfs出距离，之后把不满足≤2的点的信息入堆处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

signed main() {
  // freopen("in", "r", stdin);
  int u, v, w;
  int n;
  while(~scanf("%d", &n)) {
    vector<vector<int>> G(n+1);
    vector<int> dp(n+1);
    for(int i = 0; i < n - 1; i++) {
      scanf("%d%d",&u,&v);
      G[u].emplace_back(v);
      G[v].emplace_back(u);
    }
    priority_queue<tuple<int,int,int>> q;
    function<void(int, int)> dfs = [&](int u, int p) {
      for(auto v : G[u]) {
        if(p == v) continue;
        dp[v] = dp[u] + 1;
        if(dp[v] > 2) q.push(make_tuple(dp[v], v, u));
        dfs(v, u);
      }
    };
    dfs(1, -1);
    int ret = 0;
    while(!q.empty()) {
      tie(w, v, u) = q.top(); q.pop();
      if(dp[v] <= 2) continue;
      ret++;
      dp[u] = 1; 
      for(auto v : G[u]) dp[v] = min(dp[u]+1, dp[v]);
    }
    printf("%d\n", ret);
  }
  return 0;
}