又被抓摆了/kk

T4(T3?)Cactus to Tree

link

Solution

tmd,连tm \(\Theta(n^2)\) 都没有看出来!!!!!!/fn

考虑 \(\Theta(n^2)\) 怎么做,其实就是对于每一个点直接 BFS(似乎对正解也没有什么启发性?听简单的,但是似乎大家都没有写)。再考虑树怎么做,你发现就是对于一个点求最远距离。

然后放在这个图上面,可以发现的其实就是如干个环通过边连在一起。那我们可以发现的是,对于环上一个点求的时候,肯定是断开距它环的一半的那条边,然后就是求每个环到环的最小最大距离,这个直接建个圆方树换根dp一下就好了,断边方法也是跟上面一样的。

似乎可以做到 \(\Theta(n)\) 不过 \(\Theta(n\log n)\) 挺好做的,所以就补的 \(\Theta(n\log n)\)

T2(T4?)[Ynoi2005] vti

link

Solution

Ynoi滚出模拟赛!!!!!/fn

纯口胡,不保证正确。我们一眼看出不会低于 \(\Theta(n\sqrt n)\),因为链的时候就是区间正序对数了,所以我们也就明白这个题目需要二次离线了(开摆 😅

我们考虑我们的答案如何计算,我们把 \(T\) 按 dfs 序排序,设 \(f(u,v)\) 表示树上 \(u\to v\) 的正序队数(\(u\)\(v\) 的父亲),那么答案即是:

\[\sum f(\text{rt},T_i)-\sum f(\text{rt},\text{lca}(T_i,T_{i+1})) \]

\(\text{rt}\) 就是所有点的 \(\text{lca}\)

那么你发现这玩意显然可以树上莫队+BIT之类的。不过这样就是 \(\Theta(n\sqrt n\log n)\) 的了。你发现可以直接二次离线,可以差分之后用分块维护一下就好了。

复杂度 \(\Theta(n\sqrt n)\)(假设 \(n,m\) 同价),感觉还是挺清新的。

原文地址:http://www.cnblogs.com/Dark-Romance/p/16829724.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性