fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define lli long long int
  4. #define inf 1000000000
  5. #define pb push_back
  6. #define mp make_pair
  7. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  8. #define endl "\n"
  9. #define yoi cout<<"yo"<<endl;
  10. #define debug(i) cout<<i<<endl;
  11. const int mod=1e9 +7;
  12. int county=0;
  13. void dfs(vector<vector<int> >&v,int i,int parent){
  14.     int j;
  15.     county++;
  16.     for(j=0;j<v[i].size();j++){
  17.         if(v[i][j]!=parent){
  18.             dfs(v,v[i][j],i);
  19.         }
  20.     }
  21. }
  22. int main(){
  23. IOS;
  24. int t;
  25. cin>>t;
  26. int h=t;
  27. while(t--){
  28.     lli n,x,y,i,j;
  29.     cin>>n;
  30.     vector<pair<int,int> > edges;
  31.     for(i=0;i<n-1;i++){
  32.         cin>>x>>y;
  33.         edges.pb({x,y});
  34.     }
  35.     int subtree=0;
  36.     for(i=1;i<(1<<(n-1));i++){
  37.         vector<vector<int> > v(n+1);
  38.         int start;
  39.         county=0;
  40.         for(j=0;j<n-1;j++){
  41.             if(i&(1<<j)){
  42.                 start=edges[j].first;
  43.                 v[edges[j].first].pb(edges[j].second);
  44.                 v[edges[j].second].pb(edges[j].first);
  45.             }
  46.         }
  47.         dfs(v,start,0);
  48.         if(county==__builtin_popcount(i)+1)
  49.             subtree++;
  50.     }
  51.     cout<<"Case #"<<h-t<<": "<<subtree<<endl;
  52. }
  53. }
  54.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8
stdout
copy 
Case #1: 3
Case #2: 66
https://ideone.com/Ps8ZAX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!