Submission #38547026

---

Source Code Expand

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

namespace vbzIO{
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    #define pb push_back
    #define pi pair<int, int>
    #define fi first
    #define se second
    #define mp make_pair
    inline int read () {
        reg char ch = gh();
        reg long long x = 0;
        reg char t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? -x : x;
    }
    inline void write(int x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
}

using vbzIO::read;
using vbzIO::write;

const int maxn = 55;
int T, n, fa[maxn][2], vis[maxn], in[maxn], lf[maxn];
struct edge { int u, v; } e[maxn];
vector<int> a[maxn], b[maxn], g[maxn], leaf;

void init() {
    memset(fa, 0, sizeof(fa));
    memset(vis, 0, sizeof(vis));
    memset(in, 0, sizeof(in));
    for (int i = 1; i <= n; i++) g[i].clear();
}

void dfs(int u, int fat, int fl) {
    fa[u][fl] = fat;
    int flg = 0;
    for (int v : (!fl ? a[u] : b[u])) {
        flg++;
        if (v == fat) continue;
        dfs(v, u, fl);
    }
    if (flg == 1 && !fl) lf[u] = 1;
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i++) b[i].clear(), a[i].clear(), lf[i] = 0;
    for (int i = 1, u, v; i <= n - 1; i++) {
        u = read(), v = read(), e[i] = { u, v };
        a[u].pb(v), a[v].pb(u);
    }
    for (int i = 1, u, v; i <= n - 1; i++) {
        u = read(), v = read();
        b[u].pb(v), b[v].pb(u);
    }
    init();
    dfs(1, 0, 0);
    dfs(1, 0, 1);
    int fl = 1;
    leaf.clear();
    for (int i = 1; i <= n; i++) 
        if (lf[i]) leaf.push_back(i);
    for (int i = 1; i <= n; i++) 
        if (fa[i][0] ^ fa[i][1]) fl = 0;
    if (fl) return puts("0"), void();
    int res = 1e9;
    for (int rt : leaf) {
        for (int nr = 1; nr <= n; nr++) {
            if (rt == nr) continue;
    // int rt = 3, nr = 1;
            for (int i = 1; i <= n; i++) a[i].clear();
            for (int i = 1; i <= n - 1; i++) {
                if (e[i].u == rt || e[i].v == rt) continue;
                a[e[i].u].pb(e[i].v), a[e[i].v].pb(e[i].u);
            }
            a[nr].pb(rt), a[rt].pb(nr);
            init(), dfs(rt, 0, 0), dfs(rt, 0, 1);
            // for (int i = 1; i <= n; i++) cout << fa[i][0] << " " << fa[i][1] << endl;
            int cnt = 0;
            for (int i = 1; i <= n; i++) 
                if (fa[i][0] ^ fa[i][1]) vis[i] = 1, cnt++;
            fl = 0;
            for (int i = 1; i <= n; i++) {
                if (!vis[i] && vis[fa[i][0]]) {
                    // cout << i << endl;
                    fl = 1;
                    break;
                }
            }
            // cout << cnt << endl;
            // if (fl) return puts("-1"), void();
            if (fl) continue;
            for (int i = 1; i <= n; i++) {
                if (!vis[i]) continue;
                if (vis[fa[i][0]]) g[i].pb(fa[i][0]), in[fa[i][0]]++;
                if (vis[fa[i][1]]) g[fa[i][1]].pb(i), in[i]++;
            }
            int sum = 0;
            queue<int> q;
            for (int i = 1; i <= n; i++) 
                if (vis[i] && !in[i]) q.push(i), sum++;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : g[u]) {
                    in[v]--;
                    if (!in[v]) q.push(v), sum++;
                }
            }
            if (sum != cnt) continue;
            // if (sum + 1 == 5) cout << rt << " " << nr << endl;
            res = min(res, sum + 1), fl = 1;
        }
    }
    write(res == 1e9 ? -1 : res);
    puts("");
}

int main() {
    T = read();
    while (T--) solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int vbzIO::read()’:
./Main.cpp:19:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   19 |         reg char ch = gh();
      |                  ^~
./Main.cpp:20:23: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   20 |         reg long long x = 0;
      |                       ^
./Main.cpp:21:18: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   21 |         reg char t = 0;
      |                  ^

Judge Result