题解 | 小红的树上删边

#include<iostream>

using namespace std;

const int N=1e5+5;

int n;
int head[N],cnt;
int siz[N];
int ans;

struct node
{
    int next;
    int to;
}edge[N<<1];

inline void addage(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void dfs1(int x,int fa)
{
    siz[x]=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs1(v,x);
        siz[x]+=siz[v];
    }
}

inline void dfs2(int x,int fa)
{
    if(siz[x]%2==0) ans+=1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs2(v,x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addage(u,v);
        addage(v,u);
    }
    if(n%2!=0)
    {
        cout<<-1;
        return 0;
    }
    dfs1(1,0);
    dfs2(1,0);
    printf("%d",ans-1);
    return 0;
}