一个树形dp的题，又是一个涉及不深的领域 = =；
不过在网上看到了大神用很巧的思路解决了这个题；
大神的思路就是：
从树的底部往上看：如果一棵子树拥有两个及以上的叶子节点，可以将这棵子树与大树分离，并且将子树化成一条直线；
为什么这样子是最优呢？我不会证明，但我觉得这种情况可以保留最多不被删除的边；
代码：
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 1000005
using namespace std; vector<int>ve[maxn];
bool v[maxn];
int ans;
int dfs(int a)
{
v[a]=;
int l=ve[a].size(),res=;
for(int i=; i<l; i++)
if(!v[ve[a][i]])
res+=dfs(ve[a][i]);
if(res>=)
{
if(a==)ans+=res-;
else ans+=res-;
return ;
}
else return ;
} int main()
{
int t,n,a,b;
scanf("%d",&t);
while(t--)
{
ans=;
scanf("%d",&n);
for(int i=; i<=n; i++)
ve[i].clear();
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
ve[a].push_back(b);
ve[b].push_back(a);
}
dfs();
printf("%d\n",*ans+);
memset(v,,sizeof v);
}
return ;
}
利用dp的思想：将整棵树拆成N个单枝(所有点的度小于2)，所需的cost即为2*N-1(拆成N个单枝需 N-1 cost，合成一个环需要 N cost)。
可用树形DP求出N最小的情况，用dp[i][j]表示以i为根的可用度为j的最小单枝数。
状态转移方程：dp[root][0]=min(dp[root][0]+dp[son][0],dp[root][1]+dp[son][1]-1)
dp[root][1]=min(dp[root][1]+dp[son][0],dp[root][2]+dp[son][1]-1)
dp[root][2]=dp[root][2]+dp[son][0]
代码：
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 1000005
using namespace std; vector<int>ve[maxn];
bool v[maxn];
int dp[maxn][];
int ans; void dfs(int a)
{
v[a]=;
dp[a][]=dp[a][]=dp[a][]=;
int l=ve[a].size();
for(int i=;i<l;i++)
{
int u=ve[a][i];
if(!v[u])
{
dfs(u);
dp[a][]=min(dp[a][]+dp[u][],dp[a][]+dp[u][]-);
dp[a][]=min(dp[a][]+dp[u][],dp[a][]+dp[u][]-);
dp[a][]=dp[a][]+dp[u][];
}
}
} int main()
{
int t,n,a,b;
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof dp);
ans=;
scanf("%d",&n);
for(int i=; i<=n; i++)
ve[i].clear();
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
ve[a].push_back(b);
ve[b].push_back(a);
}
dfs();
ans=min(dp[][],min(dp[][],dp[][]));
printf("%d\n",*ans-);
memset(v,,sizeof v);
}
return ;
}