wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
LCT重轻边切换次数证明
? 数据结构 ?
2017-03-20 07:24:47
416
0
0
wuvin
? 数据结构 ?
%%%whx 我们称LCT上是轻边而且正常树剖结果中也是轻边的边为**轻轻边**。 LCT上是轻边而且正常树剖中是重边的边为**轻重边**。 单次Access的重轻切换次数等于该路径上**轻轻边**和**轻重边**的和。 轻轻边的复杂度是有保证的，不超过$logn$条。 我们采用势能分析**轻重边**的总量变。 每次一条**轻重边**会变成**重重边**，然而**重重边**只有在Access到相邻这个点上的时候才能被变成**轻重边**。所以我们每次把**轻轻边**成**重轻边**的时候支付多余的一次时间费用。由于**轻轻边**是有保证的，所以**重轻边**也是有保证的。 于是总共的切换次数不超过$nlogn$ 有点绕，不过还能看。。。。（~~别打我~~） 继续去问武爷如何把$logn$卡满，然后武爷给了一个特别妙的主意—— 建一颗满二叉树，每次插入时从根往下沿着虚边走，然后就可以了。
上一篇:
lyoj 211 「雅礼集训 2017 Day8」共
下一篇:
1more头戴式耳机测评
0
赞
416 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册