surajumang08

GGBHAItester

Jan 24th, 2017
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<cstring>
  5. #include<queue>
  6. using namespace std;
  7. vector<vector<int> >graph (100001 );
  8. bool restr[100001];
  9. bool visited[100001];
  10. queue<int>Q;
  11. long long total;
  12. void bfs(int level)
  13. {
  14.   //traversal always starts with node 1
  15.   int node;
  16.   do
  17.   {
  18.     queue<int> ql;
  19.     while(!Q.empty())
  20.     {
  21.       node=Q.front();
  22.       Q.pop();
  23.       /* if(visited[node])
  24.         continue;*/
  25.  
  26.       visited[node]=1;
  27.  
  28.       if(restr[node])
  29.         total+=(level*2);
  30.  
  31.       for(int i=0; i<graph[node].size(); i++ )
  32.       {
  33.          if(visited[graph[node][i]])
  34.           continue;
  35.  
  36.  
  37.  
  38.           ql.push(graph[node][i]);
  39.       }
  40.  
  41.  
  42.     }
  43.     Q=ql;
  44.     level++;
  45.  
  46.   }while(!Q.empty());
  47. }
  48.  
  49. int main()
  50. {
  51.   int t,n,m,a,b;
  52.   cin>>t;
  53.   while(t--)
  54.   {
  55.     cin>>n>>m;
  56.  
  57.     graph.clear();
  58.     graph.resize(100001);
  59.     for(int i=1;i<n;i++)
  60.     {
  61.       cin>>a>>b;
  62.       graph[a].push_back(b);
  63.       graph[b].push_back(a);
  64.     }
  65.     memset(restr,0,sizeof(restr));
  66.     for(int i=0;i<m;i++)
  67.     {
  68.       cin>>a;
  69.       restr[a]=1;
  70.     }
  71.     memset(visited,0,sizeof(visited));//all are unvisited initially
  72.  
  73.     Q.push(1);
  74.     total=0;
  75.     bfs(0);
  76.     double ans=(1.0/m)*total;
  77.     printf("%.6f\n",ans );
  78.   }
  79. }
Add Comment
Please, Sign In to add comment