#include using namespace std; #define NMAX 10004 #define LGMAX 19 #define KMAX 605 #define INF 0x3f3f3f3f int LG [NMAX << 1], EulerTour[NMAX << 1], EulerLvl [NMAX << 1], First [NMAX << 1], RMQ[NMAX << 2][LGMAX], N, K, Pos = 0; vector A[NMAX], G[KMAX]; int Cost[KMAX][KMAX], Cap[KMAX][KMAX], Depth[NMAX]; bool InQueue[KMAX]; long long F[KMAX][KMAX]; long long D[KMAX]; bool Used[KMAX]; int T[KMAX]; vector Sp, Sv; queue Q; void EulerTraversal(int x, int depth) { EulerTour[++Pos] = x; EulerLvl [Pos] = depth; First [x] = Pos; Depth [x] = depth; for ( vector::iterator it = A[x].begin(); it != A[x].end(); ++it ) { if (First[*it]) continue; EulerTraversal(*it, depth + 1); EulerTour[++Pos] = x; EulerLvl [Pos] = depth; } } void BuildRMQ() { LG[1] = 0; for ( int i = 2; i <= Pos; i++ ) LG[i] = LG[i/2] + 1; for ( int i = 1; i <= Pos; i++ ) { RMQ[i][0] = i; } for ( int j = 1; (1 << j) <= Pos; j++ ) { for ( int i = 1; i + (1 << (j-1)) <= Pos; i++ ) { RMQ[i][j] = RMQ[i][j-1]; if (EulerLvl[RMQ[i + (1 << (j-1))][j-1]] < EulerLvl[RMQ[i][j]]) { RMQ[i][j] = RMQ[i + (1 << (j-1))][j-1]; } } } } inline int LCA(int x, int y) { int xPos = First[x], yPos = First[y]; if (xPos > yPos) { int tmp = xPos; xPos = yPos; yPos = tmp; } int L = LG[yPos - xPos + 1]; int sol = RMQ[xPos][L]; if (EulerLvl[RMQ[yPos - (1 << L) + 1][L]] < EulerLvl[RMQ[xPos][L]]) { sol = RMQ[yPos - (1 << L) + 1][L]; } return EulerTour[sol]; } long long Augment(int source, int sink) { memset(Used, 0, sizeof(Used)); memset(D, INF, sizeof(D)); Used[source] = 1; D[source] = 0; Q.push(source); while (!Q.empty()) { int x = Q.front(); Q.pop(); for ( int i = 0; i < G[x].size(); i++ ) { int y = G[x][i]; if (Cap[x][y] - F[x][y] > 0 && D[x] + Cost[x][y] < D[y]) { D[y] = D[x] + Cost[x][y]; T[y] = x; if (!Used[y]) { Used[y] = 1; Q.push(y); } } } Used[x] = 0; } if (D[sink] == INF) return 0; long long fmin = INF; for ( int i = sink; i != source; i = T[i] ) fmin = min(fmin, Cap[T[i]][i] - F[T[i]][i]); for ( int i = sink; i != source; i = T[i] ) { F[T[i]][i] += fmin; F[i][T[i]] -= fmin; } return fmin * D[sink]; } int main() { //freopen("test.in", "r", stdin); cin >> N >> K; for ( int i = 1, x; i <= K; i++ ) { cin >> x; Sp.push_back(x); } for (int i = 1, x; i <= K; i++) { cin >> x; Sv.push_back(x); } for (int i = 1, x, y; i < N; i++) { cin >> x >> y; A[x].push_back(y); A[y].push_back(x); } EulerTraversal(1, 0); BuildRMQ(); for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { int x = Sp[i]; int y = Sv[j]; int lca = LCA(x, y); int dist = Depth[x] + Depth[y] - 2 * Depth[lca]; G[i].push_back(j+K); G[j+K].push_back(i); Cost[i][j+K] = dist; Cost[j+K][i] = -dist; Cap[i][j+K] = 1; } } // 2*K + 1 = src // 2*K + 2 = dst int src = K + K + 1; int dst = K + K + 2; for (int i = 0; i < K; i++) { G[src].push_back(i); G[i].push_back(src); Cost[src][i] = 0; Cost[i][src] = 0; Cap[src][i] = 1; } for (int i = K; i < K+K; i++) { G[i].push_back(dst); G[dst].push_back(i); Cost[dst][i] = Cost[i][dst] = 0; Cap[i][dst] = 1; } long long partial; long long total = 0; while (partial = Augment(src, dst)) { total = max(total, partial); } cout << total << '\n'; return 0; }