#include #include #include const int inf = 100000000; //#include using namespace std; typedef struct celula { int nod; celula *next; } *lista; lista graf[10005], v; int i, j, n, k, stramos[10005][15], lev[10005], sp[305], serv[305]; int viz[10005]; // typedef struct { int nod, dist; } tip; tip heap[100000]; lista graf1[605]; int cap[605][655], cost[655][655], s, d, dist[655], coada[1300000], aux[655], tata[655], sol, hp, newdist[655], st, en; //---------- void dfs(int nod, int l) { viz[nod] = 1; lev[nod] = l; for (lista p = graf[nod]; p; p = p->next) if (viz[p->nod] == 0) { dfs(p->nod, l + 1); stramos[p->nod][0] = nod; } } int levelup(int x, int l) { for (int i = 14; i >= 0; --i) if (lev[stramos[x][i]] >= l) x = stramos[x][i]; return x; } int lca(int x, int y) { if (lev[x]= 0; --i) if (stramos[x][i] != stramos[y][i]) { x = stramos[x][i]; y = stramos[y][i]; } return stramos[x][0]; } } int distanta(int x, int y) { int aux = lca(x, y); return lev[x] - lev[aux] + lev[y] - lev[aux] + 1; } //----------- void swap(int x, int y) { tip w = heap[x]; heap[x] = heap[y]; heap[y] = w; } void upheap(int nod) { while (nod>1 && heap[nod].dist <= heap[nod / 2].dist) { swap(nod, nod / 2); nod /= 2; } } void downheap(int nod) { bool ok = 1; while (2 * nod + 1 <= hp&&ok){ ok = 0; int mmin = min(heap[nod].dist, min(heap[2 * nod].dist, heap[2 * nod + 1].dist)); if (mmin == heap[2 * nod].dist) { ok = 1; swap(nod, 2 * nod); nod *= 2; } else if (mmin == heap[2 * nod + 1].dist) { ok = 1; swap(nod, 2 * nod + 1); nod *= 2; ++nod; } } if (2 * nod == hp&&heap[2 * nod].distnext) if (cap[nod][p->nod]>0) { int v = cost[nod][p->nod] + dist[nod] - dist[p->nod]; if (newdist[p->nod]>v + newdist[nod]) { newdist[p->nod] = v + newdist[nod]; tata[p->nod] = nod; baga(p->nod, newdist[p->nod]); aux[p->nod] = aux[nod] + cost[nod][p->nod]; } } } } return(viz[d]); } //---------------------- int main(void) { // freopen("file.in","r",stdin); scanf("%d %d", &n, &k); for (i = 1; i <= k; ++i) scanf("%d", &sp[i]); for (i = 1; i <= k; ++i) scanf("%d", &serv[i]); for (i = 1; i>x>>y; scanf("%d %d", &x, &y); v = new celula; v->nod = x; v->next = graf[y]; graf[y] = v; v = new celula; v->nod = y; v->next = graf[x]; graf[x] = v; } dfs(1, 1); for (j = 1; (1 << j) <= n; ++j) for (i = 1; i <= n; ++i) stramos[i][j] = stramos[stramos[i][j - 1]][j - 1]; //imi construiesc graful pentru flux maxim de cost minim for (i = 1; i <= k; ++i) for (j = k+1; j <= 2*k; ++j){ v = new celula; v->nod = i; v->next = graf1[j]; graf1[j] = v; v = new celula; v->nod = j; v->next = graf1[i]; graf1[i] = v; cap[i][j] = 1; cost[i][j] = distanta(sp[i], serv[j-k])-1; cost[j][i] = -cost[i][j]; } //adaug sursa 0 si detinatia 2*k+1 s = 0; d = 2 * k + 1; for (i = 1; i <= k; ++i) { v = new celula; v->nod = s; v->next = graf1[i]; graf1[i] = v; v = new celula; v->nod = i; v->next = graf1[s]; graf1[s] = v; cap[s][i] = 1; cost[s][i] = 0; cost[i][s] = 0; } for (i = k + 1; i <= 2 * k; ++i) { v = new celula; v->nod = d; v->next = graf1[i]; graf1[i] = v; v = new celula; v->nod = i; v->next = graf1[d]; graf1[d] = v; cap[i][d] = 1; cost[i][d] = 0; cost[d][i] = 0; } //acum fac flux maxim de cost minim memset(viz, 0, sizeof(viz)); n = 2 * k + 1; st = 1; en = 1; coada[en] = s; for (i = 1; i <= n; ++i) dist[i] = inf, viz[i] = 0; dist[s] = 0; viz[s] = 1; while (st <= en) { int nod = coada[st]; for (lista p = graf1[nod]; p; p = p->next) if (dist[p->nod]>dist[nod] + cost[nod][p->nod] && cap[nod][p->nod]>0) { dist[p->nod] = dist[nod] + cost[nod][p->nod]; if (viz[p->nod] == 0) { ++en; coada[en] = p->nod; viz[p->nod] = 1; } } viz[nod] = 0; ++st; } //caut drumuri de ameliorare de cost minim cu Dijkstra while (exista_drum()){ int q = d, mmin = inf; for (i = 1; i <= n; ++i) dist[i] = aux[i]; while (q != s) { mmin = min(mmin, cap[tata[q]][q]); q = tata[q]; } sol += mmin*dist[d]; q = d; while (q != s) { cap[tata[q]][q] -= mmin; cap[q][tata[q]] += mmin; q = tata[q]; } } printf("%d",sol); // _getch(); return 0; }