Tree with Small Distances(cf1029E)(树形动规)

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

Sample Output1

Sample Input2

Sample Output2

Sample Input3

Sample Output3

题意：

给你一棵树，让你从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}^{j\in son_i}min(dp[j][0],dp[j][1],dp[j][2])\)

如果选这个点，它的儿子的状态就无关了，取最小值就可以了。

\(dp[i][2]=\sum_j^{j\in son_i}dp[j][0]\)

如果这个点不选且要使这个点不被覆盖，就只能取它的儿子的0状态更新。

这两条方程还是比较好推的。主要是0状态比较难转移。

我们可以分类，若他的儿子中有一个点\(j\)满足\(dp[j][1]<dp[j][0]\)，就有

\(dp[i][0]=\sum_{j}^{j\in son_i}min(dp[j][0],dp[j][1])\)

注意这里不能用儿子的2状态转移，这会导致那个点不被覆盖

但如果没有儿子满足，我们可以在他的儿子中找一个点\(k\)，使\(dp[k][1]-dp[k][0]\)最小，然后使

\(dp[i][0]=\sum_{j}^{j\in 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]);

}

巴特西