你的朋友弗兰克正在玩电子游戏。现在他正在迷宫中寻找宝藏，这个迷宫中有且只有一个宝藏。这个迷宫可以被视为一个无向联通图有 n 节点n - 1条边即是一棵树。你的朋友法兰克真的不擅长迷宫，作为一个老司机，你决定帮他一把。但你所能做的就是在顶点中放置一些路标来引导他走正确的路。只要弗兰克到达了有路标的节点，就会沿着正确的路走一步到达到下一个节点(接近宝藏一步)，并且再也不会回到这个节点。如果节点上没有路标，则他下一步会随机等概率选择一条边移动到相邻的节点(随机游走)。你希望通过放置一些路标在节点上使得弗兰克到达宝藏的期望步数最小，求弗兰克最小期望步数。
第一行三个正整数 N, K, S (1 <= N <= 100000, 0 <= K <= 50,1 <= S <= N)
N 表示图中点的个数，K 表示你最多可以防止 K 个路标，S 表示弗兰克的起点，宝藏始终在1号节点。
接下来N - 1行每行一个正整数，第 i 行 Ei 表示有一条边从i + 1连接到 Ei(1 <= Ei <= i)。
一个正整数代表最小期望步数。
4 0 3 1 2 3
8
5 1 5 1 2 3 4
6
这道题你会答吗？花几分钟告诉大家答案吧！
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
