void path_add(int u, int v, int z) {
int fu = top[u], fv = top[v];
while (fu != fv) {
if (dep[fu] >= dep[fv]) update(1, 1, n, dfn[top[u]], dfn[u], z), u = fa[top[u]];
else update(1, 1, n, dfn[top[v]], dfn[v], z), v = fa[top[v]];
fu = top[u];
fv = top[v];
}
if (dfn[u] >= dfn[v]) update(1, 1, n, dfn[v], dfn[u], z);//这里
else update(1, 1, n, dfn[u], dfn[v], z);
}
为什么打注释的那行换作深度比较就会RE,跳到同一条重链上后dfn序不是应该随着深度增加吗?
int fu = top[u], fv = top[v];
while (fu != fv) {
if (dep[fu] >= dep[fv]) update(1, 1, n, dfn[top[u]], dfn[u], z), u = fa[top[u]];
else update(1, 1, n, dfn[top[v]], dfn[v], z), v = fa[top[v]];
fu = top[u];
fv = top[v];
}
if (dfn[u] >= dfn[v]) update(1, 1, n, dfn[v], dfn[u], z);//这里
else update(1, 1, n, dfn[u], dfn[v], z);
}
为什么打注释的那行换作深度比较就会RE,跳到同一条重链上后dfn序不是应该随着深度增加吗?