无可奈何花落去

Luogu

IDLGP9346

Time2000ms

Memory512MB

DifficultyP5

洛谷原创O2优化背包 DP树形 DP组合数学洛谷月赛

望向树上的花朵：一朵花有 $n$ 瓣花瓣，花瓣之间有 $n-1$ 条边连接，所有的花瓣都是连通的。树上的花瓣随着春天的离开而凋落。具体地，每一天，都会在未断开的边中均匀随机地选择一条边断开。当每个花瓣的度数均不超过 $2$ 时，我们称这朵花凋零了。一朵花期望会在几天后凋零呢？ ## Input 第一行一个正整数 $n$，表示花瓣的数量。第二行 $n-1$ 个正整数 $f_2,\dots,f_n$，表示花瓣 $f_i$ 与花瓣 $i$ 之间有一条边。 ## Output 一行，一个正整数，表示一朵花的期望凋零时间，对 $985661441$（是个质数捏）取模。如果你不会分数取模，请参考[此题](https://www.luogu.com.cn/problem/P2613)。 [samples] ## Background 天上下起了蒙蒙小雨，回家已是傍晚，推开院门，一地花瓣映入眼帘，随着最近几天花瓣的凋落，树上的花瓣已所剩无几。从地上捡起一片花瓣，干涩的双眼立刻充满了泪水，它顺着脸颊滑下。落到花上的，不知是雨还是泪...... ## Note **【样例 1 解释】** 可以发现第一次不管断开哪条边，均会使这朵花凋零，故期望凋零时间为 $1$。 **【样例 2 解释】** 第一次断开 $(1,2)$ 或 $(2,4)$ 或 $(2,5)$，凋零时间为 $1$；第一次断开 $(1,3)$，凋零时间为 $2$。故期望凋零时间为 $\frac{3}{4}\times 1+\frac{1}{4}\times 2=\frac{5}{4}$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（1 point）：$f_i=i-1$。 - Subtask 2（12 points）：$n\leq 8$。 - Subtask 3（12 points）：$n\leq 18$。 - Subtask 4（8 points）：$f_i=1$。 - Subtask 5（16 points）：有且仅有 $1$ 号点度数大于 $2$。 - Subtask 6（13 points）：$n\leq 50$。 - Subtask 7（13 points）：$n\leq 100$。 - Subtask 8（13 points）：$n\leq 500$。 - Subtask 9（12 points）：无特殊限制。对于 $100\%$ 的数据，$1\le n\leq 5\times 10^3$，$f_i<i$。

Samples

Input #1

4
1 2 2

Output #1

Input #2

5
1 1 2 2

Output #2

739246082

Input #3

19
1 2 3 4 5 6 1 8 9 10 11 12 1 14 15 16 17 18

Output #3

246415365

Input #4

49
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 11 13 13 15 1 21 7 20 16 4 3 11 11 24 24 31 33 29 24 21 22 12 27 18 37 25 28 26 22 36 38 29

Output #4

587033383

API Response (JSON)

{
  "problem": {
    "name": "无可奈何花落去",
    "description": {
      "content": "望向树上的花朵：一朵花有 $n$ 瓣花瓣，花瓣之间有 $n-1$ 条边连接，所有的花瓣都是连通的。 树上的花瓣随着春天的离开而凋落。具体地，每一天，都会在未断开的边中均匀随机地选择一条边断开。 当每个花瓣的度数均不超过 $2$ 时，我们称这朵花凋零了。 一朵花期望会在几天后凋零呢？",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9346"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "望向树上的花朵：一朵花有 $n$ 瓣花瓣，花瓣之间有 $n-1$ 条边连接，所有的花瓣都是连通的。\n\n树上的花瓣随着春天的离开而凋落。具体地，每一天，都会在未断开的边中均匀随机地选择一条边断开。\n\n当每个花瓣的度数均不超过 $2$ 时，我们称这朵花凋零了。\n\n一朵花期望会在几天后凋零呢？\n\n## Input\n\n第一行一个正整数 $n$，表示花瓣的数量。\n\n第二行 $n-1$ 个正整数 $f_2,\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments