如果使用虚数做法并在搜索后统计答案,仍需记录一条边是原图上的还是新建的,而不是通过是否为祖先判断,否则部分询问可能结果偏大。
例如:
4 3 1 2 1 2 2 3 3 4 1 4 1 4 2 3
应为
4
而不是:
6
因为建立虚树时2,3也被添加,此时 1->4 的新边与 1->2->3->4 可能被重复统计
2
3