解答：

思路：首先这题是一个树的分解问题，题目明确给了分解的要求就是分解后连通部分的结点数目是偶数。这句可以得到特殊情况，如果总结点数目是奇数，那么直接输出-1即可，如果是偶数继续往下分析。

题目还要求删除边的个数最多，那么问题转换为删除若干条边后使得连通部分结点个数是偶数且尽可能最小，最小不就是2！这仅限于某些情况，有可能是4...继续我们树的性质得到子树的结点的奇偶性不会影响父亲结点的奇偶性，例如以结点s为根，（包含s自己在内）所有后代结点数加和为奇数，假设其一个子树结点个数加和为偶数，奇数加偶数还是奇数。反之偶数加偶数还是偶数，所以只要子树的结点个数是偶数直接与其根节点分裂即可。

那么具体做法就是先DFS遍历树的结构，从叶子节点开始一步步往上递归如果子树的结点个数能被2整除就分割次数加一，不能被分割就把子树的结点个数加到父亲结点上。至此你应该可以发现需要用后序遍历序列，“左右根”从最后面最靠右开始往回统计计数。

存储连通关系，“连通这个词直接联想到图论”那就用邻接表存储即可，由于是无向图，那么要存储两遍一条边。这题也比较巧合正好n个点n-1条边，是最小生成树，那么就不存在成环的可能性，直接深搜一路畅通无阻。

特别注意在遍历时要跳过回到父亲结点的可能性，不然会爆栈，这样就保证不会走回头路，至此思路全部结束，我们来算一下时间复杂度

递归的时间复杂度是要看递归代码到底在干一件什么事情：这里递归就是把每个结点作为根节点遍历一遍，那么就是O(n)，完全满足题目要求n<=10^5。

空间复杂度（只针对于邻接表不考虑栈空间）：如果是一棵斜树那么数组的长度就是树的高度O(n)，正常情况下树的高度为O(logn)

下面提供了Lambda表达式和定义函数的版本，可以根据需求自行观看。

#include<bits/stdc++.h>
using namespace std;
#define int long long


void solve(){
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);//邻接表存图
    int ans=0;
    int u,v;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    if(n%2!=0){
        cout<<-1<<endl;
        return;
    }
    auto dfs=[&](auto&&self,int u,int parent)->int{
        int uSize=1;
        for(int k:g[u]){
            if(k==parent){
                continue;
            }
            int vSize=self(self,k,u);
            if(vSize%2==0){
                ans++;
            }else{
                uSize+=vSize;
            }
        }
        return uSize;
    };

    dfs(dfs,1,-1);
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<vector<int>>g;//邻接表存图
int ans=0;

int dfs(int u,int parent){//树的后序遍历
    int uSize=1;//记录当前结点初始为1个
    for(int k:g[u]){
        if(k==parent){//如果迭代到是父亲就跳过避免走回头路
            continue;
        }
        int vSize=dfs(k,u);//以当前的u作为父亲，k作为孩子继续递归调用
        if(vSize%2==0){//该子树的结点个数是偶数就分割
            ans++;
        }else{//不是偶数就加到父亲中
            uSize+=vSize;
        }
    }
    return uSize;//最后返回当前结点的子树大小为了递归调用
}

void solve(){
    cin>>n;
    g.resize(n+1);
    int u,v;
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    if(n%2!=0){
        cout<<-1<<endl;
        return;
    }
    int res=dfs(1,-1);
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}