Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<queue>
- #include<cstdio>
- #define ll long int
- using namespace std;
- int main() {
- int t;
- scanf("%d", &t);
- while(t--) {
- ll n, m, u, v;
- scanf("%ld%ld", &n, &m);
- vector< vector<ll> > a(n);
- vector<ll> level(n);
- for(ll i = 0; i < n-1; i++) {
- scanf("%ld%ld", &u, &v);
- u--; v--;
- a[u].push_back(v);
- a[v].push_back(u);
- }
- vector<bool> isRestaurant(n, false);
- for(ll i = 0; i < m; i++) {
- scanf("%ld", &u);
- u--;
- isRestaurant[u] = true;
- }
- queue<ll> q;
- q.push(0);
- ll l = 0;
- level[0] = 0;
- vector<bool> visited(n, false);
- ll total = 0;
- do {
- queue<ll> q1;
- while(!q.empty()) {
- ll node = q.front();
- q.pop();
- level[node] = l;
- if(isRestaurant[node]) {
- total += 2*l;
- }
- visited[node] = true;
- for(vector<ll>::iterator it = a[node].begin(); it != a[node].end(); ++it) {
- if(!visited[*it])
- q1.push(*it);
- }
- }
- l++;
- q = q1;
- }while(!q.empty());
- double ans = 1.0/m * total;
- printf("%.6f\n", ans);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment