按照我们之前的经验,仙人掌上问题往往可以通过圆方树转化为树上问题。 我们发现,最短路在树上是一种非常容易解决的 …
lp3320 SDOI2015 寻宝游戏
我们找到了这样一个结论: 「一个树上点集构成的最小生成树中,若两点间有路径,则此两点的DFS序在树上相近。」 …
lp2597 ZJOI2012 灾难
这一题的思路还是比较清晰的。虽然可以当作支配树模板,但是事实上可以上一个LCA来代替支配树。具体来说,就是把有 …
lp1967 NOIP2013 货车运输
一道最大生成树加LCA的裸题。 因为是求路上权值最小的边权值最大,所以可以在最大生成树上跑。当然二分答案加01 …