fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 100005;
  5. vector<int> adj[MAXN];
  6. bool isPho[MAXN];
  7. bool valid[MAXN];
  8. int N, M;
  9.  
  10. void prune(int node, int parent) {
  11.     valid[node] = isPho[node];
  12.     for (int neighbor : adj[node]) {
  13.         if (neighbor != parent) {
  14.             prune(neighbor, node);
  15.             valid[node] = valid[node] || valid[neighbor];
  16.         }
  17.     }
  18. }
  19.  
  20. pair<int, int> dfs(int node, int parent) {
  21.     pair<int, int> farthest = {0, node}; 
  22.     for (int neighbor : adj[node]) {
  23.         if (neighbor != parent && valid[neighbor]) {
  24.             pair<int, int> result = dfs(neighbor, node);
  25.             result.first += 1; 
  26.             if (result.first > farthest.first) {
  27.                 farthest = result;
  28.             }
  29.         }
  30.     }
  31.     return farthest;
  32. }
  33.  
  34. int main() {
  35.     cin >> N >> M;
  36.     vector<int> pho_restaurants(M);
  37.     for (int i = 0; i < M; i++) {
  38.         cin >> pho_restaurants[i];
  39.         isPho[pho_restaurants[i]] = true;
  40.     }
  41.     for (int i = 0; i < N - 1; i++) {
  42.         int u, v;
  43.         cin >> u >> v;
  44.         adj[u].push_back(v);
  45.         adj[v].push_back(u);
  46.     }
  47.     prune(pho_restaurants[0], -1);
  48.     int start = pho_restaurants[0];
  49.     while (!valid[start]) start++;
  50.     pair<int, int> first_dfs = dfs(start, -1);
  51.     int farthest_node = first_dfs.second;
  52.     pair<int, int> second_dfs = dfs(farthest_node, -1);
  53.     int longest_path = second_dfs.first;
  54.     int pruned_node_count = 0;
  55.     for (int i = 0; i < N; i++) {
  56.         if (valid[i]) pruned_node_count++;
  57.     }
  58.     int result = 2 * (pruned_node_count - 1) - longest_path;
  59.     cout << result << endl;
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 5756KB
comments (?)
stdin
copy 
8 5
0 6 4 3 7
0 1
0 2
2 3
4 3
6 1
1 5
7 3
stdout
copy 
7
https://ideone.com/nILfZq
language:
C++14 (clang 8.0)
created:
2 days 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!