Ankit_132

F

Oct 12th, 2023
480
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll     long long
  7. #define pb     push_back
  8. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  9.  
  10. int main()
  11. {
  12.     _test
  13.     {
  14.         int n, k;
  15.         cin>>n>>k;
  16.  
  17.         vector<int> x(k), mark(n);
  18.         for(auto &e: x)     cin>>e;
  19.  
  20.         for(auto e: x)      mark[e-1] = 1;
  21.  
  22.         vector<vector<int>> tree(n);
  23.  
  24.         for(int i=0; i<n-1; i++)
  25.         {
  26.             int u, v;
  27.             cin>>u>>v;
  28.  
  29.             u--, v--;
  30.  
  31.             tree[u].pb(v);
  32.             tree[v].pb(u);
  33.         }
  34.  
  35.         vector<int> lowestMark(n, -1);
  36.  
  37.         function<void(int, int)> DFS = [&](int u, int p)
  38.         {
  39.             if(mark[u])     lowestMark[u] = 0;
  40.  
  41.             for(auto v: tree[u])
  42.             {
  43.                 if(v == p)      continue;
  44.  
  45.                 DFS(v, u);
  46.  
  47.                 if(lowestMark[v] != -1)
  48.                     lowestMark[u] = max(lowestMark[u], 1+lowestMark[v]);
  49.             }
  50.         };
  51.  
  52.  
  53.         DFS(0, -1);
  54.  
  55.         int ans = 1e9;
  56.  
  57.         function<void(int, int, int)> DFS2 = [&](int u, int p, int topM)
  58.         {
  59.             multiset<int> mst;
  60.             mst.insert(-1);
  61.  
  62.             int mmax = max(topM, lowestMark[u]);
  63.  
  64.             ans = min(ans, max(topM, lowestMark[u]));
  65.  
  66.             if(mark[u])     mst.insert(0);
  67.  
  68.             for(auto v: tree[u])
  69.             {
  70.                 if(v == p)      continue;
  71.  
  72.                 if(lowestMark[v] != -1)
  73.                     mst.insert(lowestMark[v]+1);
  74.             }
  75.  
  76.             int tmp;
  77.  
  78.             for(auto v: tree[u])
  79.             {
  80.                 if(v == p)      continue;
  81.  
  82.                 tmp = -1;
  83.  
  84.                 if(topM != -1)      tmp = topM + 1;
  85.                 if(mark[u])         tmp = max(tmp, 1);
  86.  
  87.                 if(lowestMark[v] != -1)
  88.                     mst.erase(mst.find(lowestMark[v]+1));
  89.  
  90.                 if(*mst.rbegin() != -1)
  91.                     tmp = max(tmp, *mst.rbegin()+1);
  92.  
  93.                 DFS2(v, u, tmp);
  94.  
  95.                 if(lowestMark[v] != -1)
  96.                     mst.insert(lowestMark[v]+1);
  97.             }
  98.         };
  99.  
  100.         DFS2(0, -1, -1);
  101.  
  102.         cout<<ans<<"\n";
  103.     }
  104. }
  105.  
Advertisement
Add Comment
Please, Sign In to add comment