fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const long long MOD = 998244353;
  5. const long long N = 2e5 + 9;
  6. const long long OO = 2e18;
  7. const double PI = acos(-1.0);
  8. #define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  9. #define int long long int
  10. #define ld long double
  11. #define ve vector<int>
  12. #define vep vector<pair<int,int>>
  13. #define graph vector<ve>
  14. #define visit vector<bool>
  15. #define db(...) 7
  16. #define fix(res, n) fixed <<  setprecision(n) << (long double)res
  17. #define tc         int testcase;   cin>>testcase;   while(testcase--)
  18. #define all(num)      (num).begin(), (num).end()
  19. #define el            cout<<(testcase?"\n":"")
  20.  
  21.  
  22. //             "وَأَن لَّيْسَ لِلْإِنسَانِ إِلَّا مَا سَعَى ﴿39﴾ وَأَنَّ سَعْيَهُ سَوْفَ يُرَى ﴿40﴾ ثُمَّ يُجْزَاهُ الْجَزَاء الْأَوْفَى "
  23. //                                  My way to My dream
  24. //#ifdef ONLINE_JUDGE
  25. //    freopen("input.txt", "r", stdin);
  26. //    freopen("output.txt", "w", stdout);
  27. //#endif
  28. //int n , m ;
  29. //bool ok (int x , int y)
  30. //{
  31. //    return x>=0&&y>=0&&x<n&&y<m;
  32. //}
  33. //ve dx={1,0,-1,0,1,-1,1,-1};
  34. //ve dy={0,1,0,-1,-1,1,1,-1};
  35. ve dx = {1, 0, -1, 0};
  36. ve dy = {0, 1, 0, -1};
  37.  
  38. ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  39. void bfs(int i, graph &g, ve &dist, set<int> &st, ve &mdist) {
  40.     queue<int> q;
  41.     q.push(i);
  42.     dist[i] = 0;
  43.     if (st.find(i) != st.end()) {
  44.         mdist.push_back(dist[i]);
  45.     }
  46.     while (!q.empty()) {
  47.         int node = q.front();
  48.         q.pop();
  49.         for (auto x: g[node]) {
  50.             if (dist[x] == -1) {
  51.                 q.push(x);
  52.                 dist[x] = dist[node] + 1;
  53.                 if (st.find(x) != st.end()) {
  54.                     mdist.push_back(dist[x]);
  55.                 }
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. signed main() {
  62.     IOS
  63.     tc {
  64.  
  65.         int n, k, start;
  66.         cin >> n >> k;
  67.  
  68.         set<int> st;
  69.  
  70.         for (int i = 0; i < k; ++i) {
  71.             int num;
  72.             cin >> num;
  73.             st.insert(num);
  74.         }
  75.  
  76.         graph g(n + 1);
  77.         ve dist(n + 1, -1),   mset,  ans(n + 1);
  78.  
  79.         for (int i = 0; i < n - 1; ++i) {
  80.             int u, v;
  81.             cin >> u >> v;
  82.  
  83.             g[u].push_back(v);
  84.             g[v].push_back(u);
  85.  
  86.         }
  87.  
  88.         for (int i = 1; i <= n; ++i) {
  89.  
  90.             if (g[i].size() == 1)
  91.                 start = i;
  92.  
  93.         }
  94.  
  95.         bfs(start, g, dist, st, mset);
  96.  
  97.         std::sort(mset.begin(), mset.end());
  98.         for (int i = 1; i <= n; ++i) {
  99.  
  100.             ans[i] = max(abs(dist[i] - mset.front()), abs(dist[i] - mset.back()));
  101.  
  102.         }
  103.  
  104.         cout << *min_element(ans.begin() + 1, ans.end());
  105.         el;
  106.     }
  107. }
Runtime error #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lyUPEZ
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!