DuongNhi99

3

Dec 21st, 2020
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int64_t long long
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 5;
  6. const int K = 2005;
  7.  
  8. typedef pair<int64_t, int> ii;
  9.  
  10. int n, k;
  11. int a[N];
  12. vector<int> graph[N];
  13.  
  14. int64_t ans;
  15. int Visited[N], Parent[N];
  16. int64_t mask[N];
  17. bool check[N];
  18.  
  19. void DFS(int u) {
  20.    Visited[u] = Visited[Parent[u]] + 1;
  21.  
  22.    if((mask[u] & (1 << Visited[u])))
  23.       check[u] = true;
  24.    mask[u] = mask[u] | (1 << Visited[u]);
  25.  
  26.    for(int v : graph[u]) {
  27.       if(v != Parent[u]) {
  28.          if(!Visited[v]) {
  29.             Parent[v] = u;
  30.             DFS(v);
  31.          }
  32.       }
  33.    }
  34. }
  35.  
  36. int main() {
  37. #ifdef LOCAL
  38.    freopen("in.txt", "r", stdin);
  39. #else
  40.    freopen("MILITARY.inp", "r", stdin);
  41.    freopen("MILITARY.out", "w", stdout);
  42. #endif
  43.    ios_base::sync_with_stdio(false);
  44.    cin.tie(0); cout.tie(0);
  45.  
  46.    cin >> n >> k;
  47.    for(int i = 1; i <= k; ++i)
  48.       cin >> a[i];
  49.  
  50.    for(int i = 1; i < n; ++i) {
  51.         int p, q;
  52.         cin >> p >> q;
  53.         graph[p].push_back(q);
  54.         graph[q].push_back(p);
  55.    }
  56.  
  57.    for(int i = 1; i <= k; ++i) {
  58.       fill(Visited + 1, Visited + n + 1, 0);
  59.       fill(Parent + 1, Parent + n + 1, 0);
  60.       DFS(a[i]);
  61.    }
  62.  
  63.    ans = 0;
  64.    for(int i = 1; i <= n; ++i)
  65.       if(!check[i]) ans++;
  66.    cout << ans << '\n';
  67.    for(int i = 1; i <= n; ++i)
  68.       if(!check[i])
  69.          cout << i << ' ';
  70.  
  71.    return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment