Tree with Small Distances

题意：

个点条边的无向连通图，问最少加多少条边才能使顶点到任意一个点不超过两条边。

思路：
一种贪心的策略是如果某个点到根结点的边数超过二就把该节点的父结点和根结点连条边

检验刚开始的策略：

连了这条边后，的边数都变成了
因为没有考虑到结点和根结点连边对父结点的影响，导致多连了一条边

正确的方案应该是下面这幅图：

所以正确的策略不仅要考虑连接某个结点后对孩子结点的影响，还要考虑对父结点的影响。
统计每个点到根的距离，从叶子结点开始判断，如果某个结点到根结点距离大于，该节点的父结点就和根结点连边，同时更改父结点以及父结点的父结点到根结点的距离。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+7,maxm=4e5+7;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int head[maxn],Next[maxm],to[maxm],tot;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int ans,hi[maxn];
void dfs(int x,int f,int dep) {
    bool flag=true;
    hi[x]=dep;
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(v==f) continue;
        dfs(v,x,dep+1);
        if(flag&&hi[v]>2) {
            hi[v]=2;
            hi[x]=1;
            hi[f]=2;
            flag=false;
            ans+=1;
        }
    }
}
int main() {
    int n=read();
    for(int i=2,u,v;i<=n;++i) {
        u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs(1,0,0);
    printf("%d\n",ans);
    return 0;
}