「AGC027F」Grafting

发表于 分类于

$Link$

有两棵树 $A,B$，每次操作你可以选择 $A$ 上一个叶子节点，删去与它相连的所有边，并在它和另一个点之间连一条边，每个点只能被操作一次。问最少需要多少次可以使得 $A$ 与 $B$ 完全相同或输出无解，$t$ 组数据。

$1\le t\le20,3\le n\le50$。

我们考虑操作点 $u$ 时连上的那一条边，因为在 $B$ 树上与 $u$ 点相连的边可能有多条，所以这条边无法确定连到哪。

但是如果我们知道了树的根，那这条边就必须连向它在 $B$ 树上的父亲了，而树根不会被操作。

所以我们枚举第一次修改的点和连向的边，把这个点作为根，那么只要一个点在 $A$ 树和 $B$ 树上的父亲不同，那这个点就需要被操作，否则不要。

可以得到有以下两个约束条件：

  • 如果点 $u$ 不需要被操作，而 $u$ 在 $A$ 树上的父亲需要，由于我们只能操作 $A$ 树的叶子节点，所以不存在合法的操作顺序。

  • 如果点 $u$ 和 $u$ 在 $A$ 树上的父亲 $a$，$u$ 在 $B$ 树上的父亲 $b$ 都要修改。假设我们在 $u$ 之后操作 $b$，那么 $u\to b$ 的边就会被删掉。所以这三个点修改的顺序应为 $b\to u\to a$。

那我们就得到了很多约束关系，根据这个约束关系建图找环即可。如果有环，则不存在合法的操作序列。

时间复杂度 $O(tn^3)$。

$code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 50;

int tt;
int n;
struct Edge {
    int from, to, next;
};
struct Tree {
    Edge	edge[(N << 1) + 1];
    int	start[N + 1], tot, fa[N + 1], d[N + 1];
    int	connect[N + 1][N + 1];
    inline void init()
	{
        for (int i = 1; i <= n; i++) {
            start[i] = d[i] = 0;
            for (int j = 1; j <= n; j++)
                connect[i][j] = 0;
        }
        tot = 0;
        return;
    }
    inline void addedge(int u, int v)
	{
        edge[++tot] = { u, v, start[u] };
        start[u] = tot;
        d[u]++;
        edge[++tot] = { v, u, start[v] };
        start[v] = tot;
        d[v]++;
        connect[u][v] = connect[v][u] = 1;
        return;
    }
    inline void dfs(int u)
	{
        for (int i = start[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v != fa[u]) {
                fa[v] = u;
                dfs(v);
            }
        }
        return;
    }
} A, B, C;
struct Graph {
    Edge	edge[(N << 1) + 1];
    int	start[N + 1], ind[N + 1], tot;
    int	vis[N + 1];
    inline void init()
	{
        for (int i = 1; i <= n; i++)
            start[i] = vis[i] = ind[i] = 0;
        tot = 0;
        return;
    }
    inline void addedge(int u, int v)
	{
        edge[++tot] = { u, v, start[u] };
        start[u] = tot;
        ind[v]++;
        return;
    }
    inline void bfs()
	{
        queue<int> q;

        for (int i = 1; i <= n; i++)
            if (!ind[i])
                q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (int i = start[u]; i; i = edge[i].next) {
                int v = edge[i].to;
                if (!vis[v]) {
                    ind[v]--;
                    if (!ind[v])
                        q.push(v);
                }
            }
        }
        return;
    }
} G;
int need[N + 1];
int ans;

inline int calc(int root)
{
    int sum = 0;

    G.init();
    A.fa[root] = B.fa[root] = root;
    A.dfs(root);
    B.dfs(root);
    for (int i = 1; i <= n; i++)
        need[i] = A.fa[i] != B.fa[i];
    for (int i = 1; i <= n; i++) {
        if (i == root)
            continue;
        if (!need[i] && A.fa[i] && need[A.fa[i]])
            return 1e9;
        if (!need[i])
            continue;
        if (B.fa[i] && need[B.fa[i]])
            G.addedge(B.fa[i], i);
        if (A.fa[i] && need[A.fa[i]])
            G.addedge(i, A.fa[i]);
        sum++;
    }
    G.bfs();
    for (int i = 1; i <= n; i++)
        if (need[i] && !G.vis[i])
            return 1e9;
    return sum;
}
int main()
{
    tt = read();

    while (tt--) {
        ans = 1e9;
        C.init();
        B.init();
        n = read();
        for (int i = 1; i < n; i++) {
            int u = read(), v = read();
            C.addedge(u, v);
        }
        for (int i = 1; i < n; i++) {
            int u = read(), v = read();
            B.addedge(u, v);
        }
        for (int i = 1; i <= n; i++) {
            if (C.d[i] == 1) {
                for (int j = 1; j <= n; j++) {
                    if (i == j)
                        continue;
                    A.init();
                    for (int k = 1; k <= C.tot; k += 2)
                        if (C.edge[k].from != i && C.edge[k].to != i)
                            A.addedge(C.edge[k].from, C.edge[k].to);
                    A.addedge(i, j);
                    ans = min(ans, calc(i) + (C.connect[i][j] ^ 1));
                }
            }
        }
        printf("%d\n", ans == 1e9?-1:ans);
    }

    return 0;
}