如果你使用动态开点线段树,进行 QS 和 QM 两个查询操作时,尝试在函数外将当前的根节点编号作为参数传入,在函数内,对于线段树上的区间查询操作,直接把传入的编号作为查询的根节点。例如:
ll query_dis_sum(int r, int u, int v) {
ll res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += query_sum(r, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res += query_sum(r, 1, n, dfn[u], dfn[v]);
return res;
}
在外面传进去: query_dis_sum(root[c[u]], u, v)
我的 WA 原因:
ll query_dis_sum(int u, int v) {
ll res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += query_sum(root[c[u]], 1, n, dfn[top[u]], dfn[u]); 一直使用了root[c[u]]
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res += query_sum(root[c[u]], 1, n, dfn[u], dfn[v]);
return res;
}
具体原因本蒟蒻也不是很懂,还请各位神犇解答
WA记录