[Blog] [Docs] [Code] [Slides] [About]

KickStart 2020 Round D-C Beauty of Tree

概率

2020-07-15 20:32 CST

题目 题解和总结:/blog/2020-07-15-ks-2020-d/

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

class Node {
 public:
  int parents[20];
  vector<int> children;
  double pA, pB;
};

int n = 0, A = 0, B = 0;
Node tree[500005] = {};

int getParent(int pos, int x) {
  int pow = 0;
  while (x) {
    if (x & 1) {
      pos = tree[pos].parents[pow];
      if (pos == 0) return 0;
    }
    x >>= 1;
    pow += 1;
  }
  return pos;
}

void dfs(int pos) {
  for (auto child : tree[pos].children) {
    dfs(child);
  }
  if (pos != 1) {
    int parentA = getParent(pos, A);
    int parentB = getParent(pos, B);
    if (parentA > 0)
      tree[parentA].pA += tree[pos].pA;
    if (parentB > 0)
      tree[parentB].pB += tree[pos].pB;
  }
}

int main() {
  int T = 0;
  scanf("%d", &T);
  memset(tree[0].parents, 0, sizeof(int) * 20);
  for (int t = 1; t <= T; ++t) {
    scanf("%d %d %d", &n, &A, &B);
    tree[1].parents[0] = 0;
    tree[1].children.clear();
    tree[1].pA = tree[1].pB = 1.0 / n;
    for (int i = 2; i <= n; ++i) {
      int p = 0;
      scanf("%d", &p);
      tree[i].parents[0] = p;
      tree[i].children.clear();
      tree[p].children.emplace_back(i);
      tree[i].pA = tree[i].pB = 1.0 / n;
    }
    for (int i = 1; i < 20; ++i) {
      for (int pos = 1; pos <= n; ++pos) {
        tree[pos].parents[i] = tree[tree[pos].parents[i - 1]].parents[i - 1];
      }
    }
    dfs(1);
    double ans = 0.0;
    for (int pos = 1; pos <= n; ++pos) {
      ans += tree[pos].pA + tree[pos].pB - tree[pos].pA * tree[pos].pB;
    }
    printf("Case #%d: %.8lf\n", t, ans);
  }
  return 0;
}
<EOF>