Game on Tree(期望线性性)

Game on Tree

题意：

有一颗树，每一步选择一个节点，则这个节点以及它的子树上所有节点都会被染色，问染色完整棵树需要的步数的期望值

分析：

由于以前没怎么做过求期望的题，我看到这题的第一想法是找出所有的染色方法，计算他们的步数的平均值，但是这样想想就很复杂…

所以正确的解法利用期望的一个性质-------期望线性性

如上图的树，每一个节点是否被染色取决于它自己以及它的祖辈节点有没有被染***r> 例如对于6号节点，只有1号，3号和6号节点会影响到它的染色情况
如果操作发生在1，3上，6号只是被间接染色，只有直接操作6号时它才是直接染***r> 所以6号节点***作的概率为1/3，又因为操作一次为一步，所以6号节点步数的期望为1*1/3=1/3

依此可推出各点的步数期望，再结合期望的线性性，求和即为答案

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
vector<int> ve[maxn];
int deep[maxn] = {0};
int vis[maxn] = {0};
void dfs(int k, int d)
{
    vis[k] = 1;
    deep[k] = d;
    for (auto v : ve[k])
    {
        if (!vis[v])
        {
            dfs(v, d + 1);
        }
    }
}
int main(int argc, char const *argv[])
{
    int n, u, v;
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        ve[u].emplace_back(v);
        ve[v].emplace_back(u);
    }
    dfs(1, 1);
    double ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += 1.0 / deep[i];
    printf("%.20f\n", ans);
    return 0;
}