您的位置: 首页 > IT文章 > 3910: 火车

3910: 火车

分类: IT文章 • 2022-04-20 14:15:34

题目链接

题目大意：n点m边，从a出发，一次经过k个点，已去过的不用去，剩下的必须依次去，求经过多少边

题解：用并查集将一段合成一个点，每个点最多只能被合一次，保证时间复杂度。查询的时候像链剖一样一段一段往上跳就行了，还要顺便把路径上的所有点缩起来。