「泉七培训 – 黄施霖」最近公共祖先

2014年6月14日4,1851

第一次做交互题。。。

可以任意询问俩点的lca,然后要求回答出树的形态,最多50000个点

各种乱搞搞了90分

首先对于一条链的情况可以用平衡树维护点之间的关系,不过如果直接写个快排也是可以的

那么对于一棵树可以这样考虑

假设我们大致知道了前i个点的情况,这时候加入一个点x

先求其与当前根root的lca设为t,如果t=x,那么fa[root]=x,ls[x]=root,root=x

否则有两种情况,x在root的左子树,或者在右子树,就可以递归下去

所以只要先选俩个点和他们的lca作为起始点然后一个个加入点即可

如果数据是随机的话,复杂度应该是nlogn

判断一条链只要递归次数远超过nlogn基本可以确定

但是由于出题人比较丧病。。一条链加一棵小树就能卡掉这种做法。。所以被卡了10分,暂时还没想到好的做法解决这种情况,大概这种做法的出发点就决定了会被卡吧,如果随机把一棵树分成俩棵什么的这样就不会在这里被卡

 

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
wyj Recent comment authors
  Subscribe  
提醒
wyj
wyj

呵呵