圆方树

前言

关于圆方树,它不配有个标签吗? 这就是这个题单存在的意义(之一)。

找不到特别多有关圆方树的题,所以只能放上来下面的几道。如果你有其他圆方树的题(或使用圆方树比较简洁的题),欢迎私信 @rui_er 进行补充!

题目简述

比较模板的一些题

P5236 【模板】静态仙人掌

经典的圆方树处理仙人掌。

建圆方树后处理比较方便的题*

*:此类题可能不需要圆方树,但是使用圆方树可以简化或更加易于理解。

P5058 [ZJOI2004]嗅探器

此题是点双的题,但是在 tarjan() 以后使用圆方树可以很方便地解决这一问题。

圆方树进阶题*

*:此部分的题以圆方树为主要,加上其他的(难度大概低于圆方树)数据结构或小技巧维护进行解题。通过做这一部分的题,可以了解圆方树的一些搭配解题的方法。

P4320 道路相遇

建圆方树,然后使用树剖或 LCT 维护即可。

UVA1464 Traffic Real Time Query System

圆方树套一个 LCA。

CF487E Tourists

建圆方树,然后使用树剖或 LCT 维护即可。

P4606 [SDOI2018]战略游戏

建圆方树,后将点权转化为边权进行解题。

P4630 [APIO2018] Duathlon 铁人两项

建圆方树,然后跑一遍树上 dp 即可。

SP2878 KNIGHTS - Knights of the Round Table

建反图,建圆方树,因为奇环不是二分图,二分图不是奇环,所以跑一遍二分图判定即可。

P6335 [COCI2007-2008#1] STAZA

感谢 @一扶苏一 给出此题

求仙人掌上单源最长路。


  1. P5236 - 【模板】静态仙人掌
  2. P5058 - [ZJOI2004] 嗅探器
  3. P4320 - 道路相遇
  4. UVA1464 - Traffic Real Time Query System
  5. CF487E - Tourists
  6. P4606 - [SDOI2018] 战略游戏
  7. P4630 - [APIO2018] 铁人两项
  8. SP2878 - KNIGHTS - Knights of the Round Table
  9. P6335 - [COCI 2007/2008 #1] STAZA