fork(3) download
copy 
  1. /*
  2.     author: kartik8800
  3. */
  4.  
  5. #include<bits/stdc++.h>
  6. #define ll long long
  7. #define pb push_back
  8. #define fr(a,b) for(int i = a; i < b; i++)
  9. #define rep(i,a,b) for(int i = a; i < b; i++)
  10. #define mod 1000000007
  11. #define inf (1LL<<60)
  12. #define all(x) (x).begin(), (x).end()
  13. #define prDouble(x) cout << fixed << setprecision(10) << x
  14. #define triplet pair<ll,pair<ll,ll>>
  15. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  16. using namespace std;
  17.  
  18. ll dp[500001][2];
  19. vector<int> tree[500001];
  20.  
  21. void whatsWithThisOPFormat(){
  22.     static int tno = 1;
  23.     cout << "Case #" <<tno++ <<": ";
  24. }
  25.  
  26. void solve(int src, int par, vector<int>& ancestors, int& dis, bool aOrb){
  27.     dp[src][aOrb] = 1;
  28.     ancestors.push_back(src);
  29.     for(int child : tree[src])
  30.     {
  31.         if(child != par)
  32.             solve(child, src, ancestors, dis, aOrb);
  33.     }
  34.     ancestors.pop_back();
  35.     int totalAncestors = ancestors.size();
  36.     if(totalAncestors >= dis){
  37.         dp[ancestors[totalAncestors - dis]][aOrb] += dp[src][aOrb];
  38.     }
  39. }
  40.  
  41. int main() {
  42.    fast_io;
  43.    ll t,n,m,x,i,j,k,q;
  44.    cin >> t;
  45.    //t = 1;
  46.    while(t--)
  47.    {
  48.         int a,b;
  49.         cin >> n >> a >> b;
  50.         fr(1,n+1)tree[i].clear();
  51.  
  52.         fr(0,n-1)
  53.         {
  54.             cin >> x;
  55.             tree[i+2].push_back(x);
  56.             tree[x].push_back(i+2);
  57.         }
  58.  
  59.         vector<int> dfsOfTree;
  60.  
  61.         solve(1,0,dfsOfTree, a, 0);
  62.         solve(1,0,dfsOfTree, b, 1);
  63.  
  64.         double ans = 0;
  65.  
  66.         for(int i = 1; i <= n; i++){
  67.             ans = (ans + 1ll*n*(dp[i][0] + dp[i][1]));
  68.             ans = (ans - 1ll*dp[i][0]*dp[i][1]);
  69.         }
  70.  
  71.  
  72.         whatsWithThisOPFormat();
  73.         prDouble (((double)ans/(double)(n*n)));
  74.         cout << '\n';
  75.    }
  76.    return 0;
  77. }
Success #stdin #stdout 0s 15380KB
comments (?)
stdin
copy 
3
8 2 3
1 1 3 4 4 3 4
10 3 4
1 1 1 1 1 1 1 1 1
4 3 1
1 2 3
stdout
copy 
Case #1: 2.6562500000
Case #2: 1.9000000000
Case #3: 2.8750000000
https://ideone.com/7YZtDb
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!