题目：戳这里
学习博客：戳这里
题意：给一个树加最少的边，使得1到所有点的距离小于等于2.
解题思路：分析样例3可以看出，如果一个点到1的距离大于2，那么建立1到该点的父亲节点的边将比直接与该点建边更优。官方题解的做法是把所有与1距离大于2的点放到大顶堆里维护，每次取出最远的点，染色与该点父节点以及与父节点相接的所有点。也就是相当于与父节点建边，距离为1，与父节点的子节点的距离就为2了，于是把这些点弹出。从大佬博客中学到一个很妙的写法，是用dfs实现这个思路，具体看代码。
附ac代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn = 2e5 + 10;
4 int dis[maxn];
5 vector<int>nu[maxn];
6 int ans = 0;
7 void dfs(int now, int pre, int cnt)
8 {
9
10 dis[now] = cnt;
11 int flag = 0;
12 for(int y : nu[now])
13 {
14 // printf("%d\n", y);
15 if(y == pre) continue;
16
17 dfs(y, now, cnt + 1);
18 if(dis[y] > 2)
19 {
20 flag = 1;
21 dis[now] = 1;
22 dis[pre] = 2;
23 }
24 }
25 ans += flag;
26
27 }
28 int main()
29 {
30 int n;
31 int u, v;
32 scanf("%d", &n);
33 for(int i = 1; i < n; ++i)
34 {
35 scanf("%d %d", &u, &v);
36 nu[u].push_back(v);
37 nu[v].push_back(u);
38 }
39 dfs(1, 1, 0);
40 printf("%d\n", ans);
41 }