首页 > 代码库 > 集训 0618

集训 0618

今天题目有些奇怪:

T1:给定A图,A图中最短路不超过P的点对在B图有边,要求构造出一组在B图上的哈密顿回路。p>=3

嗯,猜结论,首先假设一定有解,然后考虑放缩,

加强一下限制,对A图做一颗生成树看是否有解,然后就发现在A树上跑一个类似黑白染色的东西每次跳步不会超过3,然后就 完了。

T2:无标号的生成树,仙人掌计数。

嗯...我不会。但是有些套路。

T3:一个森林,要求支持link,cut,以及查询距离根最远点个数。

LCT维护子树信息,这题稍恶心。

 

集训 0618