CF839C Journey 题解

题目链接：CF839C Journey

题意：

在七大王国里有 \(n\) 个城市和 \(n-1\) 条道路，每条道路连接两个城市，并且通过这些道路我们可以从任何一个城市到达任何一个城市。

cxy 和她的妹纸在第一个城市骑上马，她们要通过这些路开始一次旅行。但是有雾，所以她们看不见她们的马带她们去了哪里。当马抵达一个城市的时候（包括第一个城市），它会去跟当前这个城市相连的城市。但是这是一匹奇怪的马，它只去她们以前没有去过的城市。在每个城市，马以相同的概率移动去上述符合要求的城市，并且当没有这样的城市（可走）时，马就停下了。

每条路的长度都是 \(1\)，旅行从城市 \(1\) 开始，问这次旅行的期望长度（旅行长度的期望值）是多少？你可以通过这个链接来阅读一些关于期望（平均）值的文字。

输入格式：

第一行包含一个整数 \(n\)（\(1 \leq n \leq 100000\)）——城市的数量。

下来是 \(n-1\) 行，这些行中的第 \(i\) 行包含两个整数 \(u\) 和 \(v\)（\(1 \leq u,v \leq n\)，\(u \ne v\)）——第 \(i\) 条边连接的城市。

保证通过这些道路可以从任何一个城市到达任何一个城市。

输出格式：

输出一个数——这次旅行长度的期望值。旅行从城市 \(1\) 开始。

当你的答案的绝对或相对误差不超过 \(10^{-6}\) 时你的答案将会被接受。

换句话说，假定你的答案是 \(a\)，标准答案是 \(b\)，当 \(\frac{|a-b|}{\max(1,b)} \leq 10^{-6}\) 时你的答案将会被接受。

考虑设 \(f(u)\) 表示 \(u\) 到其子树的期望，则转移方程如下： \[ f(u) = \frac{1}{|\mathtt{son}(u)|}\times\sum_{v \in \mathtt{son}(u)}(f(v) + 1) \] 边界 \(f(l) = 0, l\in \mathtt{leaves}\) ，最终答案为 \(f(1)\) 。时间复杂度 \(\mathcal{O}(n)\) 。

题目本身是很简单的，因此这篇题解主要是提醒自己做dp题时候的问题：过于想当然，且忘记树形dp的要点。

问题要求是从 \(1\) 到各个节点，但是dp状态的设计与 \(1\) 无关。原因显然是不好dp。

所以在设计dp方程时，尤其是树形dp，要注意如何利用树良好的递归性质，从 \(u\) 及其子树着手设计。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

double f[N]; vector<int> vec[N];
void dfs(int u,int fa)
{
    int cnt = 0;
    for(int v : vec[u])
    {
        if(v == fa) continue;
        dfs(v,u); f[u] += (f[v] + 1); ++cnt;
    }
    if(cnt) f[u] /= (double)cnt;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, u,v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    dfs(1,0); cout << fixed << setprecision(10) << f[1] << '\n';
    return 0;
}