fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. vector<vector<int>> adj;
  6. vector<int> needed;
  7. int totalMoves = 0;
  8.  
  9. // returns true if subtree contains special/needed node
  10. bool dfs(int node, int parent) {
  11.     bool has = needed[node];
  12.     for (int nxt : adj[node]) {
  13.         if (nxt == parent) continue;
  14.         if (dfs(nxt, node)) {
  15.             totalMoves += 2;
  16.             has = true;
  17.         }
  18.     }
  19.     return has;
  20. }
  21.  
  22. int main() {
  23.     ios::sync_with_stdio(false);
  24.     cin.tie(nullptr);
  25.  
  26.     int N, k;
  27.     cin >> N >> k;
  28.  
  29.     vector<int> S(k);
  30.     for (int &x : S) cin >> x;
  31.  
  32.     adj.assign(N + 1, {});
  33.     needed.assign(N + 1, 0);
  34.  
  35.     for (int i = 0; i < N - 1; i++) {
  36.         int u, v;
  37.         cin >> u >> v;
  38.         adj[u].push_back(v);
  39.         adj[v].push_back(u);
  40.     }
  41.  
  42.     // Mark S as needed
  43.     for (int x : S) needed[x] = 1;
  44.  
  45.     // Force root (1) as needed
  46.     needed[1] = 1;
  47.  
  48.     totalMoves = 0;
  49.     dfs(1, 0);
  50.  
  51.     cout << totalMoves << "\n";
  52.     return 0;
  53. }
  54. /*8 2
  55. 5 6
  56. 1 2
  57. 2 5
  58. 2 3
  59. 2 6
  60. 1 4
  61. 4 7
  62. 7 8
  63. */
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
8 2
5 6
1 2
2 5
2 3
2 6
1 4
4 7
7 8
stdout
copy 
6
https://ideone.com/GPYMtu
language:
C++14 (clang 8.0)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!