/* * kSpecialists.c * * Created on: Mar 24, 2015 * Author: user */ #include int apa[10001], szint[10001], seen[10001], edges[10001][10001], dist[300][300], agents[300], servers[300], n, k, sol = 0, found; void dfs(int node, int sz) { int i; seen[node] = 1; szint[node] = sz; for (i = 1; i <= edges[node][0]; i++) { if (!seen[edges[node][i]]) { apa[edges[node][i]] = node; dfs(edges[node][i], sz+1); } } } void initAll() { int i, j; for (i = 0; i <= n; i++) { apa[i] = 0; szint[i] = 0; seen[i] = 0; if (i < n) for (j = 0; j <= n; j++) edges[i][j] = 0; } } void checkEdges() { int i, j; for (i = 0; i < n; i++) { for (j = 0; j <= n; j++) printf("%d %d ", i, edges[i][j]); printf("\n"); } printf("\n"); } void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } int lca(int x, int y) { int i = x, j; while (i != 1) { j = y; while (j != 1) { if (i == j) return i; j = apa[j]; } i = apa[i]; } return i; } int getDistance(int x, int y) { if (szint[x] > szint[y]) swap(&x, &y); return szint[x] + szint[y] - 2 * szint[lca(x, y)]; } void checkDist() { int i, j; for (i = 0; i < k; i++) { for (j = 0; j < k; j++) { printf("%d ", dist[i][j]); } printf("\n"); } } int getMin(int x) { int i, min1 = 10000, min2 = 10000; for (i = 0; i < k; i++) if (min1 > dist[x][i]) min1 = dist[x][i]; for (i = 0; i < k; i++) if (min2 > dist[i][x]) min2 = dist[i][x]; if (min1 > min2) return min1; else return min2; } void testMin() { int m = 0, i; k = 3; dist[0][0] = 11; dist[0][1] = 11; dist[0][2] = 11; dist[1][0] = 1; dist[1][1] = 1; dist[1][2] = 1; dist[2][0] = 1; dist[2][1] = 1; dist[2][2] = 1; for (i = 0; i < k; i++) if (m < getMin(i)) m = getMin(i); printf("%d", m); } int main(){ int i, j, a, b, m; setbuf(stdout, NULL); scanf("%d%d", &n, &k); for (i = 0; i < k; i++) { scanf("%d", &agents[i]); } for (i = 0; i < k; i++) { scanf("%d", &servers[i]); } initAll(); for (i = 1; i < n; i++) { scanf("%d%d", &a, &b); edges[a][++edges[a][0]] = b; edges[b][++edges[b][0]] = a; } dfs(1, 0); for (i = 0; i < k; i++) for (j = 0; j < k; j++) dist[i][j] = getDistance(agents[i], servers[j]); for (i = 0; i < k; i++) { m = getMin(i); if (m > sol) sol = m; } printf("%d\n", sol); return 0; }