某岛

… : "…アッカリ～ン . .. . " .. .
August 2, 2012

【套题】QTREE 系列

Brief description:

… QTREE 系列一共 5 题，都是与树有关的数据结构题：
… QTREE 是最经典的树链剖分模型，有极多的派生，必须仔细研究并熟练掌握所有方法 。。。
QTREE2 的解法要利用到倍增祖先数组，这也是一个比较常见的策略，可以用来解决诸如次小生成树之类的问题。。
QTREE3~5 涉及黑白树问题，既树中每个点分成黑色和白色，
QTREE3 询问距离根结点最近的黑色结点，QTREE4 询问全局最远的两个白色结点，QTREE5 询问距离某结点最近的白色结点。。
（其中 QTREE4 是整个系列中最困难的一题，建议先调试好没有边权的 Hide 。。
（另外 QTREE3 有正版和盗版之分。。为整理方便。。。正版的 QTREE3 也就是 PT07J 将放在 Play With Tree 系列的报告里。。。

Analysis:

Level 1：
QTREE 1

Level 2:
QTREE 2

Level 3:
QTREE 3、QTREE 4、QTREE 5

External link:

http://www.spoj.pl/problems/QTREE/
http://www.spoj.pl/problems/QTREE2/
http://www.spoj.pl/problems/QTREE3/
http://www.spoj.pl/problems/QTREE4/
http://www.spoj.pl/problems/QTREE5/

http://hi.baidu.com/sillycross/blog/item/b5d482cb51277e710eb34567.html

Posted by xiaodao
Category: 快晴

5 Comments to “【套题】QTREE 系列”

  1. 木子日匀
    August 5, 2012

    mark…
  2. Hi_World
    August 20, 2012

    すごい /$:owo
  3. 求助者
    September 16, 2012

    Hi，我看了你QTREE2的程序碼，你只用了倍增演算法，跟我的想法不一樣。
    假如是像這程序碼的想法，我該怎樣來完成Kth的操作呢？？ /$:Orz
    PS：程序碼里樹鏈剖分的實作用了BFS。
  4. xiaodao
    September 16, 2012

    妳好。。樹鏈剖分是處理樹上詢問問題的通用方法。。這個題也是可以用的。。方法就是記錄深度先從 x 跳鏈到 lca 位置，確定 kth 在左鏈還是友鏈。。然後再下降壹次做 Rank (k) 就行了。。。（具體的話您可以參考下 Hlworld 這個題的程序碼。。 /$:^ ^

    http://hlworld.diandian.com/post/2012-03-26/17452276
  5. 求助者
    September 16, 2012

    /$:~_~ 非常感謝！！！

Leave a Comment



« | »

  • Archives

    open all | close all