题解 | #生成树#

考察知识点：生成树

本题其实不用建树，对比两棵树的差异即可，当生成树 a 有而生成树 b 没有的边的数量不等于生成树 a 没有而生成树 b 有的边的数量时输出 -1（事实上，可以证明对于两棵节点相同的生成树，这两个值一定相等），否则输出相差边数之和的一半。

时间复杂度：

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    while (cin >> n)
    {
        set<pii> s;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            s.insert({u, v});
        }
        int ans = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v;
            cin >> u >> v;
            if (s.count({u, v}))
                s.erase({u, v});
            else if (s.count({v, u}))
                s.erase({v, u});
            else
                ans++;
        }
        if (ans != s.size())
            cout << -1 << endl;
        else
            cout << ans << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}