警示后人

倍增跳跃的过程中，一定要特别注意特殊情况的处理，多连几条边也不少连，有以下几种可能出错的特殊情况：

$u=v$ ，这时候必须用原图上的点 $u,v$ 连边。
$u, v$ 同步深度后，如果 $u=v$ ，直接退出，不要在 $u, v$ 的倍增虚拟节点上连边。
$u, v$ 同步深度后，如果 LCA 就是它们的直接父亲，不能只在原图上它们的父亲节点上连边，否则不会包含 $u, v$ ，应该连接 $u, v$ 的倍增虚拟节点 $fa[\ ][0]$ 。
注意，如果上述情况下一开始就有 $u, v$ 深度相同，那么 $u, v$ 同时不被包含。

原错误代码：

CPP

if(in) add_edge(to, fa[u][0].to);
else add_edge(fa[u][0].to, to);

更正后代码：

CPP

if(in){
	add_edge(to, fa[u][0].in);
	add_edge(to, fa[v][0].in);
}else{
	add_edge(fa[u][0].out, to);
	add_edge(fa[v][0].out, to);
}

Hack 数据

PLAIN

3 2 1
2 1 2 100
1 2 2 3 3 2

PLAIN

0 100 102

PLAIN

4 2 2
2 1 2 100
1 1 1 3 3 2

PLAIN

100 0 102 -1

PLAIN

4 3 1
2 1 2 100
2 2 3 20
1 2 3 4 4 3

PLAIN

0 100 120 103

PLAIN

4 3 4
2 1 2 100
2 1 3 20
1 2 3 4 4 3

PLAIN

3 3 3 0