Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int64_t long long
- using namespace std;
- const int N = 1e5 + 5;
- const int K = 2005;
- typedef pair<int64_t, int> ii;
- int n, k;
- int a[N];
- vector<int> graph[N];
- int64_t ans;
- int Visited[N], Parent[N];
- int64_t mask[N];
- bool check[N];
- void DFS(int u) {
- Visited[u] = Visited[Parent[u]] + 1;
- if((mask[u] & (1 << Visited[u])))
- check[u] = true;
- mask[u] = mask[u] | (1 << Visited[u]);
- for(int v : graph[u]) {
- if(v != Parent[u]) {
- if(!Visited[v]) {
- Parent[v] = u;
- DFS(v);
- }
- }
- }
- }
- int main() {
- #ifdef LOCAL
- freopen("in.txt", "r", stdin);
- #else
- freopen("MILITARY.inp", "r", stdin);
- freopen("MILITARY.out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- cin >> n >> k;
- for(int i = 1; i <= k; ++i)
- cin >> a[i];
- for(int i = 1; i < n; ++i) {
- int p, q;
- cin >> p >> q;
- graph[p].push_back(q);
- graph[q].push_back(p);
- }
- for(int i = 1; i <= k; ++i) {
- fill(Visited + 1, Visited + n + 1, 0);
- fill(Parent + 1, Parent + n + 1, 0);
- DFS(a[i]);
- }
- ans = 0;
- for(int i = 1; i <= n; ++i)
- if(!check[i]) ans++;
- cout << ans << '\n';
- for(int i = 1; i <= n; ++i)
- if(!check[i])
- cout << i << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment