既见君子

同济医学生的起落落落落人生记录

Heavy Light Decomposition

Heavy Light Decomposition
给你一棵二叉树,先按照常识剖分出轻重边,q个操作
每次删掉一个叶子
再求所有重边下端的点权之和

n,q<=100000

题解:
1.首先可以离线,处理出每一个点删除的时间
2.为了方便我们把时间倒过来,就变成了加入某个点的时间
3.在每个点开一个set,表示这棵子树加入了节点的时间们,然后set启发式合并上去这一步是保证nlogn^2的。
4.考虑我们拿到这些时间可以来干什么?我们可以求出每一个时间对于每一个点它到底是选了左儿子还是右儿子(或者已经没有儿子或者没有这个点都可以知道)
5.而后再利用差分思想,只用算出这个时刻和上一个时刻答案的差值,到时候for一遍就得到了每一个时刻的答案啦
6.then我们巧妙地发现如果我们是对每个点for这个点的所有时间(从set里从小到大拿出来),这个复杂度是O(sigma size(i)*logn)的,显然一条链的时候就挂了。
7.此时邱老师告诉了我一个非常巧妙的性质,就是我们只用for min(min(size[lson],size[rson])*2+1,size[u]),而后到底选哪边是能够确定的,百思不得其解,而后在tangyuhao的提示下发现的确是这样先假设左右不相等,我们假设左子树更小,那么左子树的SZ[l]=min(size[lson],size[rson]),所以右子树的SZ[r]>=SZ[l]+1
那么又假设此时已经for了min(min(size[lson],size[rson])*2+1,size[u])这么多次,有一下几种情况
(1)左子树的全部都已经提出来for过了,此时右边显然for了SZ[l]+1个,但是右边还有加入的点,那么一定右边重
(2)左子树只是for了一部分,甚至没for,此时右边却for了>SZ[l]+1,而后无论左边怎么加,都永远不可能超过SZ[l],也就永远不可能是左儿子更重
综上,在size[lson]!=size[rson]时,min(size[lson],size[rson])*2+1之后一定确定了重边的方向,至于再min一个size[u]是有可能两边size一样啦,这样我们就只有暴力完啦,但是复杂度呢是不会爆的,为什么不会爆是因为如果所有节点都必须这样全暴力那意味着这棵树形态接近完全二叉树,树高log,完全可以接受。
8.有了这个巧妙的性质那么经观察得到你在统计答案用的时间其实是和启发式合并的时间同阶的,所以也是O(nlogn^2)
9.总时间复杂度 O(nlogn^2)撒花~
10.理解完了这道题太开心,但是发现没有办法交这道题真是沮丧.

ps:邱老师太厉害啦%%%

评论
©既见君子
Powered by LOFTER