You are given an undirected tree consisting of (n) vertices. An undirected tree is a connected undirected graph with (n−1) edges.
Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex 1 to any other vertex is at most 2 . Note that you are not allowed to add loops and multiple edges.
Input
The first line contains one integer (n) ((2 le n le 2 cdot 10^5 2≤n≤2⋅1e5))-the number of vertices in the tree.
The following (n - 1) lines contain edges: edge (i) is given as a pair of vertices (u_i, v_i)((1 le u_i, v_i le n)).
It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.
Output
Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex 1 to any other vertex at most 2 . Note that you are not allowed to add loops and multiple edges.
Sample Input1
7
1 2
2 3
2 4
4 5
4 6
5 7
Sample Output1
2
Sample Input2
71
1 2
1 3
2 4
2 5
3 6
1 7
Sample Output2
0
Sample Input3
7
1 2
2 3
3 4
3 5
3 6
3 7
Sample Output3
1
题意：
给你一棵树，让你从1往其他节点连边，使得1到任意节点的距离都小于等于2
题解：
我们设
(dp[i][0])为不选(i)向根节点建边但以(i)为根的子树（包括(i)）都被覆盖的最小费用
(dp[i][1])为选(i)向根节点建边且以(i)为根的子树都被覆盖的最小费用
(dp[i][2])为不选(i)向根节点建边但以(i)为根的子树（不包括(i)）都被覆盖的最小费用
然后我们可以愉悦的列出DP方程
(dp[i][1]=1+sum_{j}^{jin son_i}min(dp[j][0],dp[j][1],dp[j][2]))
如果选这个点，它的儿子的状态就无关了，取最小值就可以了。
(dp[i][2]=sum_j^{jin son_i}dp[j][0])
如果这个点不选且要使这个点不被覆盖，就只能取它的儿子的0状态更新。
这两条方程还是比较好推的。主要是0状态比较难转移。
我们可以分类，若他的儿子中有一个点(j)满足(dp[j][1]<dp[j][0])，就有
(dp[i][0]=sum_{j}^{jin son_i}min(dp[j][0],dp[j][1]))
注意这里不能用儿子的2状态转移，这会导致那个点不被覆盖
但如果没有儿子满足，我们可以在他的儿子中找一个点(k)，使(dp[k][1]-dp[k][0])最小，然后使
(dp[i][0]=sum_{j}^{jin son_i}dp[j][0]qquad +dp[k][1]-dp[k][0])
就行了 。
#include<bits/stdc++.h>
using namespace std;
int n;
int tot,bian[400010],nxt[400010],head[200010];
int v[200010];
inline int read(){
register char c;register int ret=0;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';ret=(ret<<1)+(ret<<3)+c-'0',c=getchar());
return ret;
}
inline void add(int x,int y){
++tot;bian[tot]=y;nxt[tot]=head[x];head[x]=tot;
}
int dp[200010][3];
void dfs1(int x,int f,int d){
for(int i=head[x];i;i=nxt[i]){
if(bian[i]==f)continue;
dfs1(bian[i],x,d+1);
}
for(int i=head[x];i;i=nxt[i]){
if(bian[i]==f)continue;
dp[x][1]+=min(min(dp[bian[i]][0],dp[bian[i]][2]),dp[bian[i]][1]);
if(dp[x][2]<1e9)dp[x][2]+=dp[bian[i]][0];
}
int mn=1e9,b=0;
for(int i=head[x];i;i=nxt[i]){
if(bian[i]==f)continue;
if(dp[bian[i]][1]<dp[bian[i]][0])dp[x][0]+=dp[bian[i]][1],b=1;
else dp[x][0]+=dp[bian[i]][0];
mn=min(mn,dp[bian[i]][1]-dp[bian[i]][0]);
}
if(!b)dp[x][0]+=mn;
if(d>1)dp[x][1]++;
}
int main()
{
// freopen("traffic.in","r",stdin);
// freopen("traffic.out","w",stdout);
n=read();
for(int i=1;i<n;++i){
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs1(1,0,0);
cout<<min(dp[1][0],dp[1][1]);
}