Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #include<cstring>
- #include<queue>
- using namespace std;
- vector<vector<int> >graph (100001 );
- bool restr[100001];
- bool visited[100001];
- queue<int>Q;
- long long total;
- void bfs(int level)
- {
- //traversal always starts with node 1
- int node;
- do
- {
- queue<int> ql;
- while(!Q.empty())
- {
- node=Q.front();
- Q.pop();
- /* if(visited[node])
- continue;*/
- visited[node]=1;
- if(restr[node])
- total+=(level*2);
- for(int i=0; i<graph[node].size(); i++ )
- {
- if(visited[graph[node][i]])
- continue;
- ql.push(graph[node][i]);
- }
- }
- Q=ql;
- level++;
- }while(!Q.empty());
- }
- int main()
- {
- int t,n,m,a,b;
- cin>>t;
- while(t--)
- {
- cin>>n>>m;
- graph.clear();
- graph.resize(100001);
- for(int i=1;i<n;i++)
- {
- cin>>a>>b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- memset(restr,0,sizeof(restr));
- for(int i=0;i<m;i++)
- {
- cin>>a;
- restr[a]=1;
- }
- memset(visited,0,sizeof(visited));//all are unvisited initially
- Q.push(1);
- total=0;
- bfs(0);
- double ans=(1.0/m)*total;
- printf("%.6f\n",ans );
- }
- }
Add Comment
Please, Sign In to add comment