KickStart 2020 Round D-C Beauty of Tree
题目 题解和总结:/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>