。。。2019110...:将方案数和距离和分开计算,方案数用容斥算,距离和就枚举树上的每条边,讨论将3个人分成两边的3种情况分别计算方案数,这条边对距离和的贡献为这条边的长度乘以总方案数,最后期望为距离和除以方案数,时空复杂度O(n)。

0 点赞 评论 收藏
分享
tiany7:第三题我用二分套二分过了90,排序,去重,然后枚举a,二分b,再套一层二分c,nlognlogn,正解貌似是先二分c再二分b,具体的证明过程就不太会了
第四题是容斥 + 组合数,后50分的输入范围是1e5,n方铁定是过不去的,跟开二维还是一维数组没什么关系。

0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了: