surajumang08

GGBHAI

Jan 24th, 2017
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #include<cstdio>
  5. #define ll long int
  6. using namespace std;
  7. int main() {
  8.     int t;
  9.     scanf("%d", &t);
  10.     while(t--) {
  11.         ll n, m, u, v;
  12.         scanf("%ld%ld", &n, &m);
  13.         vector< vector<ll> > a(n);
  14.         vector<ll> level(n);
  15.         for(ll i = 0; i < n-1; i++) {
  16.             scanf("%ld%ld", &u, &v);
  17.             u--; v--;
  18.             a[u].push_back(v);
  19.             a[v].push_back(u);
  20.         }
  21.         vector<bool> isRestaurant(n, false);
  22.         for(ll i = 0; i < m; i++) {
  23.             scanf("%ld", &u);
  24.             u--;
  25.             isRestaurant[u] = true;
  26.         }
  27.         queue<ll> q;
  28.         q.push(0);
  29.         ll l = 0;
  30.         level[0] = 0;
  31.         vector<bool> visited(n, false);
  32.         ll total = 0;
  33.         do {
  34.             queue<ll> q1;
  35.             while(!q.empty()) {
  36.                 ll node = q.front();
  37.                 q.pop();
  38.                 level[node] = l;
  39.                 if(isRestaurant[node]) {
  40.                     total += 2*l;
  41.                 }
  42.                 visited[node] = true;
  43.                 for(vector<ll>::iterator it = a[node].begin(); it != a[node].end(); ++it) {
  44.                     if(!visited[*it])
  45.                         q1.push(*it);
  46.                 }
  47.             }
  48.             l++;
  49.             q = q1;
  50.         }while(!q.empty());
  51.         double ans = 1.0/m * total;
  52.         printf("%.6f\n", ans);
  53.     }
  54.     return 0;
  55. }
Add Comment
Please, Sign In to add comment