首页 > 神奇的迷宫
开通博客写题解
头像 Deep_Dark_FAntasy♂
发表于 2020-10-13 11:37:15
思路：这道题首先是求关于路径的情况，我们需要直到用题目中已知所有的WL，为了求出最终的期望，我们应该求出每一个L的概率Pl,这是对某个路径长度的全部情况在树上求解，显然是用点分治处理。用母函数的角度来考虑f(x)=a0x^0+a1x^1+a2x^2+...+an-1x^n-1，a是概率以u为当前根结 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 范艺杰
发表于 2020-10-10 00:07:07
题目可以简化为ans[i]表示距离为i的点对个数的概率和，求出这个概率和即可。考虑使用点分支分解整棵树，然后在子树中选取深度小的进行启发式合并，这里合并用ntt进行加速。复杂度O(nlognlogn)。 #include <cstdio> #include <algorithm&g 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 xyq0220
发表于 2020-10-13 16:18:35
牛客练习赛71 E- 神奇的迷宫 题意 给一颗个点的树，每条边的长度均为，Alice和Bob两人依次传送到树的某两个结点。对于任意一个人，传送到点的概率为，假设两人传送到的结点之间的最短距离为，那么他们挑战这个树的困难度为。 问他们挑战这个树的困难度的期望是多少。 分析 令表示两人最短距离为的概率 展开全文
去ta的博客 赞 (3) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”