蓝桥杯B组C++ J逃跑
作者:
每天吃不饱
,
2023-06-10 13:26:12
,
所有人可见
,
阅读 244
#include <bits/stdc++.h>
using i64 = long long;
const int MAXN = 100005;
std::vector<int> graph[MAXN];
bool isJumpboard[MAXN];
int depth[MAXN];
double dfs(int node, int parent, double prob) {
double total = 0;
int jumpCount = isJumpboard[node] ? 1 : 0;
for (int i = 0; i < graph[node].size(); i++) {
int nextNode = graph[node][i];
if (nextNode != parent) {
total += dfs(nextNode, node, prob * (1.0 - (jumpCount > 0 ? prob : 0)));
jumpCount += isJumpboard[nextNode] ? 1 : 0;
}
}
return total + prob * depth[node];
}
void solve() {
int n, m;
double p;
std::cin >> n >> m >> p;
for (int i = 0; i < n - 1; i++) {
int x, y;
std::cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
depth[i] = graph[i].size() == 1 ? 0 : MAXN;
}
std::vector<int> jumpboards(m);
for (int i = 0; i < m; i++) {
std::cin >> jumpboards[i];
isJumpboard[jumpboards[i]] = true;
}
for (int i = 0; i < m; i++) {
int node = jumpboards[i];
while (node != 1) {
node = graph[node][0];
depth[node] = std::min(depth[node], depth[graph[node][0]] + 1);
}
}
double answer = dfs(1, 0, p);
std::cout << std::fixed << std::setprecision(2) << answer << std::endl;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
solve();
return 0;
}
寄了,0通过