fork(3) download
  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
stdin
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
Case #1: 2.6562500000
Case #2: 1.9000000000
Case #3: 2.8750000000