SPOJ QTREE2

阿阿阿阿阿阿阿阿。。。总算做出来了。。错误这一个那一个的,调试的快疯了。。
大意:
一棵带权树,有两种询问:
(1):Dist(a,b)询问a到b的距离
(2):Kth(a,b,k)询问a到b的路径上的第一k个点。。
分析:
用传统的RMQ+对每个节点记录第2^i个(i=0、1、2…)祖先的在线做法,
时间是NlogN。。比较慢。。。
我的办法是首先Tarjan求出所有询问中a和b的lca。。然后dist可以直接算,
kth就需要看第k个节点是在a的祖先还是b的祖先,可以归结为求一个节点的第几个祖先的问题,
可以再dfs一遍。。用一个deque储存根到当前节点的路径。就可以离线KO了。。。
不过在码代码的时候我精神失常。。错误一箩筐。。。
Code:http://ideone.com/p9PZ8PvR

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>