Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pb push_back
- #define _test int _TEST; cin>>_TEST; while(_TEST--)
- int main()
- {
- _test
- {
- int n, k;
- cin>>n>>k;
- vector<int> x(k), mark(n);
- for(auto &e: x) cin>>e;
- for(auto e: x) mark[e-1] = 1;
- vector<vector<int>> tree(n);
- for(int i=0; i<n-1; i++)
- {
- int u, v;
- cin>>u>>v;
- u--, v--;
- tree[u].pb(v);
- tree[v].pb(u);
- }
- vector<int> lowestMark(n, -1);
- function<void(int, int)> DFS = [&](int u, int p)
- {
- if(mark[u]) lowestMark[u] = 0;
- for(auto v: tree[u])
- {
- if(v == p) continue;
- DFS(v, u);
- if(lowestMark[v] != -1)
- lowestMark[u] = max(lowestMark[u], 1+lowestMark[v]);
- }
- };
- DFS(0, -1);
- int ans = 1e9;
- function<void(int, int, int)> DFS2 = [&](int u, int p, int topM)
- {
- multiset<int> mst;
- mst.insert(-1);
- int mmax = max(topM, lowestMark[u]);
- ans = min(ans, max(topM, lowestMark[u]));
- if(mark[u]) mst.insert(0);
- for(auto v: tree[u])
- {
- if(v == p) continue;
- if(lowestMark[v] != -1)
- mst.insert(lowestMark[v]+1);
- }
- int tmp;
- for(auto v: tree[u])
- {
- if(v == p) continue;
- tmp = -1;
- if(topM != -1) tmp = topM + 1;
- if(mark[u]) tmp = max(tmp, 1);
- if(lowestMark[v] != -1)
- mst.erase(mst.find(lowestMark[v]+1));
- if(*mst.rbegin() != -1)
- tmp = max(tmp, *mst.rbegin()+1);
- DFS2(v, u, tmp);
- if(lowestMark[v] != -1)
- mst.insert(lowestMark[v]+1);
- }
- };
- DFS2(0, -1, -1);
- cout<<ans<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment