树形动态规划

//by NeighThorn
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=100+5;
int n,hd[maxn],to[maxn*2],nxt[maxn*2],cnt,f[maxn][3];
inline int read(void){
    char ch=getchar();int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f*x; 
}
inline void add(int x,int y){
    to[cnt]=y;
    nxt[cnt]=hd[x];
    hd[x]=cnt++;
}
//f[i][0]代表以i为根的子树每个顶点都在且仅在一个环中的ans
//f[i][1]代表以i为根的子树除去根节点外每个顶点都在且仅在一个环中的ans
//f[i][2]代表以i为根的子树除去根节点以及与根相连的一条链之外（也就是加上根节点至少有2个vertices)的ans
//f[i][1]=∑(k)f[to[i]][0]
//f[i][2]=∑(k-1)f[to[i]][0]   +(1)min(f[to[i]][1],f[to[i]][2])
//f[i][0]=∑(k-2)f[to[i]][0]   +(2)min(f[to[i]][1],f[to[i]][2])+1
//f[i][0]=∑(k-1)f[to[i]][0]   +(1)f[to[i]][2]+1
inline void dfs(int root,int fa){
    int sum=0,min1=inf,min2=inf,minver2=inf;
    for(int i=hd[root];i!=-1;i=nxt[i])
        if(to[i]!=fa){
            dfs(to[i],root);
            sum+=f[to[i]][0];
            minver2=min(minver2,f[to[i]][2]-f[to[i]][0]);
            if(min(f[to[i]][2]-f[to[i]][0],f[to[i]][1]-f[to[i]][0])<min1)
                min2=min1,min1=min(f[to[i]][2]-f[to[i]][0],f[to[i]][1]-f[to[i]][0]);
            else if(min(f[to[i]][2]-f[to[i]][0],f[to[i]][1]-f[to[i]][0])<min2)
                min2=min(f[to[i]][2]-f[to[i]][0],f[to[i]][1]-f[to[i]][0]);
        }
    f[root][1]=sum;
    f[root][2]=sum+min1;
    f[root][0]=sum+1+min(min1+min2,minver2);
}
signed main(void){
    while(scanf("%d",&n)!=EOF){
        cnt=0,memset(hd,-1,sizeof(hd));
        for(int i=1,x,y;i<n;i++)
            x=read(),y=read(),add(x,y),add(y,x);
        memset(f,0,sizeof(f)),dfs(1,-1);
        cout<<(f[1][0]>=inf?-1:f[1][0])<<endl;
    }
    return 0;
}