fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define sc(x) scanf("%d",&x);
  4. #define pr(x) printf("%d \n",x);
  5. #define scll(x) scanf("%lld",&x);
  6. #define scll2(x,y) scanf("%lld %lld",&x,&y);
  7. #define prll(x) printf("%lld \n",x);
  8. #define sc2(x,y) scanf("%d %d",&x,&y);
  9. #define ll long long
  10. #define PB push_back
  11. #define MP make_pair
  12. #define PII  pair<int,int>
  13. #define ff first
  14. #define ss second
  15.  
  16. using namespace std;
  17.  
  18. vector<int> gr[100000+10];
  19. int par[100000+10];
  20. int cor,ans,k;
  21.  
  22. void dfs(int n, int p=-1){
  23.     if(par[n]==p) cor++;
  24.     for(auto x: gr[n]){
  25.         if(x!=p) 
  26.             dfs(x, n);
  27.     }
  28. }
  29.  
  30. void dfs2(int n, int p=-1){
  31.     if(cor>=k) ans++;
  32.     for(auto x: gr[n]){
  33.         if(x!=p){
  34.             if(par[x]==n) cor--;
  35.             if(par[n]==x) cor++;
  36.             dfs2(x, n);
  37.             if(par[x]==n) cor++;
  38.             if(par[n]==x) cor--;
  39.         }
  40.     }
  41. }
  42.  
  43. int main(){
  44.     int tc;sc(tc)
  45.     int n,g;
  46.     int x,y;
  47.  
  48.     while(tc--){
  49.         sc(n)
  50.         ans=cor=0;
  51.         for(int i=0;i<=n;i++) gr[i].clear(), par[i]=0;
  52.  
  53.         for(int i=0;i<n-1;i++){
  54.             sc2(x,y)
  55.             gr[x].PB(y);
  56.             gr[y].PB(x);
  57.         }
  58.         sc2(g,k)
  59.         for(int i=0;i<g;i++){
  60.             sc2(x,y)
  61.             par[y]=x;
  62.         }
  63.         dfs(1);
  64.         dfs2(1);
  65.         int g = __gcd(ans, n);
  66.         if(ans==0) cout<<"0/1"<<endl;
  67.         else cout<<ans/g<<"/"<<n/g<<endl;
  68.     }
  69. }
Success #stdin #stdout 0s 18800KB
comments (?)
stdin
copy 
2
4
1 2
1 3
3 4
2 2
1 2
3 4
3
1 2
1 3
2 2
1 2
1 3
stdout
copy 
1/2
1/3
https://ideone.com/J2iK4n
language:
C++14 (gcc 8.3)
created:
7 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!