我是网络流锰锌，这道题折磨了我很久。
我们发现这里面每条边可选可不选，并且都有一定的限制条件，于是我们的思路可以往网络流方面靠拢。那么题目要求最大化，我们发现用最大流并不好做，于是考虑转化为最小割。其中要割的边就是我们要选的边数。
根据套路很自然的我们先考虑将 \(S\) 向每个点连边，每条边流量为 \(1\)，意思是选这条边的代价。思路清晰的，我们考虑有哪些限制。首先，我们选一条连接叶子的边，那么必须将上面的边全部选上，为了满足这个条件，我们把每个条边上面连接的边向自己连边，边权为无限，因为这样如果我们要割掉一条边，那么上面的边显然也要割掉，不然这是无意义的。
然后最难的地方是如何处理电机的两端。我们需要建出两个中至少选择一个的关系。我们可以将图改造一下，把第二棵树代表边的每个点向 \(T\) 连边，边权为 \(1\)，再把每个儿子向父亲连边，边权为无限，然后对于电机两端的点，我们将第一棵树的店连向第二棵树的店，流量也为无限。我们发现，这样子建图就非常合理，可以满足需要的关系。
这样子建图的边数仅仅是 \(\mathcal{O}(n)\) 级别的，所以很容易跑过。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 10000000000000000
#define pii pair <int, int>
using namespace std;
const int N = 5e4 + 5;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, a, b, p[N], x[N], q[N], y[N], s, t;
namespace mf
{
int h[N], to[N], nxt[N], val[N], tot = 1;
int dep[N];
queue <int> q;
void init ()
{
rep (i, 0, t) h[i] = 0;
tot = 1;
}
void add (int u, int v, int w)
{
to[++ tot] = v;
val[tot] = w;
nxt[tot] = h[u];
h[u] = tot;
to[++ tot] = u;
val[tot] = 0;
nxt[tot] = h[v];
h[v] = tot;
}
int bfs ()
{
q.push (s);
rep (i, 0, t) dep[i] = 0;
dep[s] = 1;
while (! q.empty ())
{
int u = q.front ();
q.pop ();
for (int i = h[u]; i; i = nxt[i])
{
int v = to[i], w = val[i];
if (! w || dep[v]) continue;
dep[v] = dep[u] + 1;
q.push (v);
}
}
return dep[t];
}
int dfs (int u, int g)
{
if (u == t) return g;
int flow = 0;
for (int i = h[u]; i; i = nxt[i])
{
int v = to[i], w = val[i];
if (! w || dep[v] != dep[u] + 1) continue;
int tmp = dfs (v, min (g, w));
flow += tmp, val[i ^ 1] += tmp;
val[i] -= tmp, g -= tmp;
}
if (! flow) dep[u] = 0;
return flow;
}
int solve ()
{
int flow = 0;
while (bfs ()) flow += dfs (s, inf);
return flow;
}
}
signed main ()
{
n = rd ();
a = rd ();
rep (i, 2, a)
{
int j = rd ();
if (j == 1) continue;
mf::add (j, i, inf);
}
rep (i, 1, n) x[i] = rd ();
b = rd ();
rep (i, 2, b)
{
int j = rd ();
if (j == 1) continue;
mf::add (i + a, j + a, inf);
}
rep (i, 1, n)
{
y[i] = rd ();
mf::add (x[i], y[i] + a, inf);
}
t = a + b + 1;
rep (i, 2, a) mf::add (0, i, 1);
rep (i, 2, b) mf::add (a + i, t, 1);
printf ("%d\n", a - 1 + b - 1 - mf::solve ());
}
/*
1
6 2 6
1 2 1 3 2 2
*/