// O(N^2) naiivne algoritm mis jalgib enda taitmisaja // Kahjuks olid lahtisel voistlusel testid suhteliselt norgad nii et sellega sai taispunktid. #include #include #include #include #include #define llong long long #define cin fin using namespace::std; int main() { clock_t begin = clock(); ifstream fin("transsis.txt"); ofstream fout("transval.txt"); int N, K; cin >> N >> K; vector > adj(N, vector(0)); vector participants(N, 0); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 0; i < K; i++) { int u; cin >> u; u--; participants[u] = 1; } fin.close(); llong answ = 2e18; for (int i = 0; i < N; i++) { // leiame iga tipu jaoks O(N) ajas transpordikulud, vastus on miinimum üle leitud väärtuste clock_t iter_start = clock(); llong sum = 0; vector visited(N, 0); queue > Q; Q.push({i, 0}); while(!Q.empty()) { auto cur = Q.front(); Q.pop(); int pos = cur.first, dist = cur.second; visited[pos] = 1; if (participants[pos]) { sum += (llong)dist * dist; } for (auto j : adj[pos]) { if (!visited[j]) { Q.push({j, dist + 1}); } } } answ = min(answ, sum); clock_t iter_end = clock(); clock_t next_iter_end = iter_end - begin + (iter_end - iter_start); if (next_iter_end >= CLOCKS_PER_SEC*0.9) break; } fout << answ; return 0; }