Advertisement
Josif_tepe

Untitled

Feb 17th, 2024
714
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <queue>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 50005;
  7. vector<pair<int, int> > graph[maxn];
  8. int imp[maxn];
  9. int cnt[maxn];
  10. int n;
  11. void bfs(int S) {
  12.     queue<int> q;
  13.     q.push(S);
  14.     q.push(0);
  15.     vector<int> parent(maxn, -1);
  16.     vector<bool> visited(n, false);
  17.     visited[S] = true;
  18.     int max_dist = 0, F = 0;
  19.     while(!q.empty()) {
  20.         int c = q.front();
  21.         q.pop();
  22.         int dist = q.front();
  23.         q.pop();
  24.         if(imp[c]) {
  25.             if(max_dist < dist) {
  26.                 max_dist = dist;
  27.                 F = c;
  28.             }
  29.         }
  30.         for(int i = 0; i < (int) graph[c].size(); i++) {
  31.             int neighbour = graph[c][i].first;
  32.             int weight = graph[c][i].second;
  33.             if(!visited[neighbour]) {
  34.                 visited[neighbour] = true;
  35.                 q.push(neighbour);
  36.                 q.push(dist + weight);
  37.                 parent[neighbour] = c;
  38.             }
  39.         }
  40.     }
  41. //    cout << max_dist <<" " << F <<  endl;
  42.    
  43.     int A = S, B = F;
  44.     while(B != A){
  45.         cnt[B]++;
  46.         B = parent[B];
  47.     }
  48.     cnt[A]++;
  49.    
  50. }
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin >> n;
  54.    
  55.     for(int i = 1; i < n; i++) {
  56.         int a, b, c;
  57.         cin >> a >> b >> c;
  58.         graph[a].push_back(make_pair(b, c));
  59.         graph[b].push_back(make_pair(a, c));
  60.     }
  61.     int k;
  62.     cin >> k;
  63.     memset(imp, false, sizeof imp);
  64.     for(int i = 0; i < k; i++) {
  65.         int x;
  66.         cin >> x;
  67.         imp[x] = true;
  68.     }
  69.     for(int i = 0; i < n; i++) {
  70.         if(imp[i]) {
  71.             bfs(i);
  72.         }
  73.     }
  74.     int res = 0, saved = 0;
  75.     for(int i = 0; i < n; i++) {
  76.         if(cnt[i] > res) {
  77.             res = cnt[i];
  78.            
  79.         }
  80.     }
  81.     for(int i = 0; i < n; i++) {
  82.        
  83.         if(cnt[i] == res) {
  84.             saved++;
  85. //            cout << i << endl;
  86.         }
  87.     }
  88.    
  89.     cout << res << " " << saved << endl;
  90.    
  91.     return 0;
  92.                
  93. }
  94. // NNNNNNNNaN
  95.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement