【泉七培训-黄施霖】最近公共祖先

2014年6月14日1,7671

第一次做交互题。。。

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

各种乱搞搞了90分

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

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

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

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

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

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

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

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

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

 

  • wyj2016年2月14日 上午10:41 回复

    呵呵

    #1