2015/2/5

leaf posted @ 2015年2月04日 21:38 in 未分类 , 447 阅读

今天终于将那道令人发指的题做掉了。。

题意是給定一棵树,在线询问编号L--R中距离点X最近的点是多少

 

首先,如果L--R固定,哪么我们检出L--R的虚树,然后询问。。那么对于L--R我们只要按1--N区间建立区间虚树,线段树查寻即可。。

 

问题看似解决了???但总感觉线结很多。。

首先怎么存区间的虚树? 我们可以对点开 vector 记录虚树dfs序即可。。。。怎么快速的在虚树上查寻?我一开始觉得很麻烦。。那些不是范围内的点怎么办?其实我们可以计算出每个不在范围内的点到在范围内的点的最短距离,这样就等价于在范围内的点了(有点想 codechef 的 BTREE)。然后怎么在dfs序中查寻距离最短的点?我们将每个点出与入记录到dfs序中,这样lower_bound待求点的dfs序号。。这样在左边的点与右边的点取min。。还有左边点的father(即自己的father)也可能成为答案。。这样就好了。。还有一种情况,就是待求点dfs序是max, 那么与虚树根节点求min即可。。

最后还被卡常数。。。时限3s 我跑了3s+。。怒开大时限。那么总的复杂度是 Nlog^2N

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter