考虑树DP，DP每个子树内的最小路径覆盖，注意到一个点有两种状态，一种是有两个儿子与他在同一条路径里，另一种是没有两个儿子与他在同一条路径里，第一种情况这个点不能与他的父亲相连，而第二种可以，所以我们f[i][j]表示以点i为根的子树，点i的状态为j时的最小路径覆盖数，通过统计儿子里有多少个在第二种状态下不比第一种状态下劣的可以简单完成转移
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 10010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long struct vec{ int to; int fro; }; vec mp[MAXN*2]; int tai[MAXN],cnt; int n; int f[MAXN][2]; inline void be(int x,int y){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; } inline void bde(int x,int y){ be(x,y); be(y,x); } void dfs(int x,int F){ int i,y; f[x][0]=f[x][1]=1; int sum=0; int tot=0; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(y!=F){ dfs(y,x); sum+=min(f[y][0],f[y][1]); if(f[y][0]<=f[y][1]){ tot++; } } } f[x][0]+=sum; f[x][1]+=sum; if(tot>=1){ f[x][0]=sum; } if(tot>=2){ f[x][1]=sum-1; } } int main(){ int i,x,y; int tmp; scanf("%d",&tmp); while(tmp--){ cnt=0; memset(tai,0,sizeof(tai)); scanf("%d",&n); memset(f,0,sizeof(f)); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); bde(x,y); } dfs(1,0); printf("%d\n",min(f[1][0],f[1][1])); } return 0; } /* */
