新加一组数据是leoly学长加的orz 虽然网上有人吐槽 但是我仍然觉得挺好的 据说这组数据是扫把形的 题意:求最大的比率即路径权值和/路径条数和的比值最大 首先这是一个分数规划的问题 考虑如何算这个最大值 我们不妨假设现在的最大值是x那么一定满足$\frac{\sum\limits_{i=1}^{n}w[i]}{n}>x$ 我们不妨去二分一下这个x 然后将其变化为$\sum\limits_{i=1}^{n}w[i]-n*x>0$ 这个数能否> 0即可 大于0说明我的最大值还可以大 那这题对于每一条路径我都可以通过枚举过根的一条路径去搞出来 所以采用点分的方法 对于这题比较卡常 所以选择在点分里面去二分这个答案 如何验证答案 我每次算出我分治块里的最大值即可 一直取max对于整个块大小< L的点我可以选择忽略 减小常数 如何去求最大能否满足条件 设f[i]表示我当前点分的时候做的这个子树深度为i的dis的最大值 这个dis我已经提前预处理的时候-mid了 g[i]表示我之前所有做过的子树中深度i的最大值是多少 每次我相当于枚举f[i]然后去g中找一个滑动的窗口中的最大值可以单调队列来搞 比较麻烦然后比较下能否> 0如果大于0直接退出即可 注意坑点:退出之后需要将f[],g[]数组重置之后再退出 关于学长这组数据卡的是什么 其实是个小tips 就是我枚举子树的时候需要从深度小的开始向深度大的枚举 这样避免了先做了大的然后每次初始化单调队列和清空f[]数组时所带来的复杂度退化 关于这部分看下代码即可明白 优化:每次二分的L直接设定成上一次的答案即可 因为我至少已经有上一次的答案了 如果不满足那么下界也是上一次的答案

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论