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

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

原错误代码：

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

更正后代码：

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 数据

输入 #1

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

输出 #1

0 100 102

输入 #2

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

输出 #2

100 0 102 -1

输入 #3

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

输出 #3

0 100 120 103

输入 #4

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

输出 #4

3 3 3 0