【链接】：
https://codeforces.com/problemset/problem/1029/E
【题意】：
用最少的连1的边使得树上每个点到1的距离不超过2
【分析】：
离1最远的点需要连边的需求越大，从叶子节点考虑，肯定是父亲连边比叶子节点连边更优。父亲连边，改变父亲的父亲的距离，重复操作。在树形dp递归的过程中完成。
【代码】：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
vector<int>v[maxn];
int dis[maxn];
int ans = 0;void dfs(int cur, int pre, int cnt) {dis[cur] = cnt;int flag = 0;for (int y : v[cur]) {if (y == pre)continue;dfs(y, cur, cnt + 1);if (dis[y] > 2) {flag = 1;dis[cur] = 1;dis[pre] = 2;}}if (flag)ans++;
}int main() {int n;scanf("%d", &n);n--;while (n--) {int x, y;scanf("%d%d", &x, &y);v[x].push_back(y);v[y].push_back(x);}dfs(1, -1 ,0);printf("%d\n", ans);
}