思路：表示我很弱，这个想不出dp方程，参考网上代码
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #define inf 1<<20 #define Maxn 110 using namespace std; int dp[Maxn][5],vi[Maxn]; vector<int> head[Maxn]; void init() { memset(dp,0,sizeof(dp)); memset(vi,0,sizeof(vi)); for(int i=0;i<=100;i++) head[i].clear(); } void dfs(int u) { int i,v,sz; vi[u]=1; sz=head[u].size(); int min1,min2,min3,sum; min1=min2=min3=inf; sum=0; for(i=0;i<sz;i++) { v=head[u][i]; if(vi[v]) continue; dfs(v); sum+=dp[v][0]; int temp=min(dp[v][1],dp[v][2])-dp[v][0]; if(temp<min1) { min2=min1; min1=temp; }else if(temp<min2){ min2=temp; } min3=min(min3,dp[v][2]-dp[v][0]); } dp[u][0]=1+sum+min(min1+min2,min3); dp[u][1]=sum; dp[u][2]=sum+min1; } int main() { int n,i,j,a,b; while(scanf("%d",&n)!=EOF) { init(); for(i=1;i<n;i++){ scanf("%d%d",&a,&b); head[a].push_back(b); head[b].push_back(a); } dfs(1); if(dp[1][0]>=inf) printf("-1 "); else printf("%d ",dp[1][0]); } return 0; }