锐客网

  1. 首页 > it技术 > >

Codeforces 280C Game on Tree

题目链接 http://codeforces.com/problemset/problem/280/C
分析 设随机变量X X X 表示操作次数， X i X_i Xi? 表示节点i i i 是否被直接操作（“是”为1 1 1，“否”为0 0 0）
显然X = ∑ 1 ≤ i ≤ n X i X = \sum_{1 \leq i \leq n} X_i X=∑1≤i≤n?Xi?，则E ( X ) = ∑ 1 ≤ i ≤ n E ( X i ) E(X) = \sum_{1 \leq i \leq n} E(X_i) E(X)=∑1≤i≤n?E(Xi?)
而一个节点被直接操作的概率等价于从仅包含该点及其祖先的集合中选出该点的概率，即1 d e p t h [ i ] 1 \over depth[i] depth[i]1?
【Codeforces 280C Game on Tree】故最终答案为∑ 1 ≤ i ≤ n 1 d e p t h [ i ] \sum_{1 \leq i \leq n} {1 \over depth[i]} ∑1≤i≤n?depth[i]1?
AC代码

#include inline int read() { int num = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num; }const int maxn = 1e5 + 5; int head[maxn], eid; struct Edge { int v, next; } edge[2 * maxn]; inline void insert(int u, int v) { edge[++eid].v = v; edge[eid].next = head[u]; head[u] = eid; }int depth[maxn]; void dfs(int u, int fa) { for (int p = head[u]; p; p = edge[p].next) { int v = edge[p].v; if (v == fa) continue; depth[v] = depth[u] + 1; dfs(v, u); } }int main() { int n = read(); for (int i = 1; i <= n - 1; ++i) { int u = read(), v = read(); insert(u, v), insert(v, u); } depth[1] = 1; dfs(1, 0); double ans = 0; for (int i = 1; i <= n; ++i) ans += 1.0 / depth[i]; printf("%f", ans); return 0; }

    推荐阅读


    上一篇：格式化日期和时间

    下一篇：魔法使的新娘