做的时候出了点锅,于是找了几个数据。
2 2
1 2 0
1 2 1
1
1 2
ans: YES
这是一个环,出错点可能在于缩点后没有更新环内的标记。
6 9
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
1 4 0
3 6 1
2 5 0
1
1 4
ans: YES
这是两个三元环中间有三条边链接,但是只有一条边是 1。可能出错的点在于缩点后搜索直接判掉了重边而没考虑边权,或者是一些其它的情况。
5 5
1 2 0
2 3 1
3 4 0
4 2 0
4 5 0
1
1 5
ans: YES
这是一个三元环的两个不同节点分别延伸出的一条边得到的两个端点的查询。出错的点可能在于倍增的时候没有把点权(缩点后内部可能有边是 1)考虑进去,并且这个数据刚刚好跳 LCA 时能直接跨过环,所以单纯在跳 LCA 的时候判断点权是不行的。
希望能给各位一点帮助,前面的求助帖我看隔一年了就不at了。