题目描述

输入

输出

样例输入

1

7

1 2

2 3

2 4

4 6

5 6

6 7

样例输出

3

---

题解

树形dp

设f[x]表示以x为根的子树完成路径覆盖，且x为某条路径的一端（可以向上延伸）的最小路径数，g[x]表示以x为根的子树完成路径覆盖，且x不为某条路径的一端的最小路径数。

那么考虑点x，只有三种情况：单独成路径、与一条子树的链成路径、与两条子树的链成路径。

这三种情况分别对应三种状态转移方程，具体见代码。

然而看到网上题解大把大把的贪心我也是醉了qaq

#include 
     
      #include 
      
       #include 
       
        #define N 10010#define inf 0x3f3f3f3fusing namespace std;int head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , son[N] , f[N] , g[N];void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void init(int x){	int i;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x])			fa[to[i]] = x , son[x] ++ , init(to[i]);}void dfs(int x){	int i , sum = 0 , t = inf;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x])			dfs(to[i]) , sum += min(f[to[i]] , g[to[i]]) , t = min(t , max(f[to[i]] - g[to[i]] , 0));	f[x] = sum + min(t , 1);	if(son[x] < 2) return;	int m1 = inf , m2 = inf;	for(i = head[x] ; i ; i = next[i])	{		if(to[i] != fa[x])		{			t = max(f[to[i]] - g[to[i]] , 0);			if(t < m1) m2 = m1 , m1 = t;			else if(t < m2) m2 = t;		}	}	g[x] = sum + m1 + m2 - 1;}int main(){	int T;	scanf("%d" , &T);	while(T -- )	{		memset(head , 0 , sizeof(head));		memset(son , 0 , sizeof(son));		memset(f , 0x3f , sizeof(f));		memset(g , 0x3f , sizeof(g));		cnt = 0;		int n , i , x , y;		scanf("%d" , &n);		for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);		init(1) , dfs(1);		printf("%d\n" , min(f[1] , g[1]));	}	return 0;}