Codeforces Round #506 (Div. 3)(Tree with Small Distances)

链接：https://codeforces.com/contest/1029/problem/E
思路：一开始想用树形dp做，但后来怎么做都有错，想法时用dp(u,f,flag)表示状态，u表示当前节点，f表示父节点，flag表示上一个节点是否与1连通.先做一遍dfs把与1节点距离在2以内的点全部先标记出来，然后如果flag为0或者与1距离位2及以内则不需要+1，否则必须连边+1，然后直到无路可走最后就是正确答案，但是不知道哪里错了= =，就有几个数据过不了不知道是哪种特殊情况没有考虑到QAQ。然后说一下官方的做法吧，直接遍历一遍，因为连通且只有n-1条边，所以到每个点的路有且仅有一条，所以距离也是唯一确定的，直接一遍dfs更新所有点的距离，然后把距离大于2的点放入一个set中，然后我们考虑，因为是有向图且只有一条路径，所以如果你连接一个点，他有可能为根节点，结果一定没有连他的父节点优，那父节点是不是一定是最优的呢，答案是肯定的，因为父节点一定要连，不然根节点就没法在距离2以内，所以我们就贪心，遍历整个set，然后找到他的父节点，连边并将+1，然后将这个父节点指向的所有其他节点（如果在set集合内）全部从set中删去，直到最终set只有一个节点，最后这个节点需要特判，直接+1即可= =，这样的贪心一定得到的是最优解
代码：

#include<bits/stdc++.h>
using namespace std;

int n;
const int maxn = 2e5+100;
vector<int> G[maxn];
//这一部分是dp代码错误的，不知道哪里错了放在这里吧- -
/*int used[maxn];
int d[maxn];
int ans = 0;

void dfs(int u,int f){
bool flag = false;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(v!=f){
            d[v] = d[u] + 1;
            dfs(v,u);
            flag|=used[v];
        }
    }
    if(d[u]>2&&!used[u]&&!flag&&!used[f]){
        used[f] = true;
        ans++;
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}*/

int d[maxn];
int f[maxn];
set<pair<int,int> > jj;

void dfs(int u,int p){
    f[u] = p;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(v!=p){
            d[v] = d[u] + 1;
            dfs(v,u);   
        }   
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++){
        if(d[i]>2)jj.insert(make_pair(-d[i],i));
    }   
    int ans = 0;
    while(!jj.empty()){
        int v = jj.begin()->second;
        v = f[v];
        ++ans;
        auto it = jj.find(make_pair(-d[v],v));//可以学习一下auto的用法
        if(it!=jj.end())jj.erase(it);
        for(auto to : G[v]){
            auto it = jj.find(make_pair(-d[to],to));
            if(it!=jj.end())
                          jj.erase(it);从set中剔除it元素
        }
    }
    printf("%d\n",ans);
    return 0;
}