Z1qqurat @ 2023-08-28 20:44:41
如果你也和我一样,那这件事情就是说把S->T的路径拆成S->lca,lca->T,然后这两部分分别用两种线段树维护贡献那要注意lca这个位置只能加一次,要不然很容易算重!!!大概这么写比较对:
for (int i = 1; i <= m; ++i) {
int u, v; scanf("%d %d", &u, &v);
int d = LCA(u, v);
t1.modify(rt1[u], 1, 5e5, dep[u], 1);
t1.modify(rt1[fa[d][0]], 1, 5e5, dep[u], -1);
int dis = dep[u] - 2 * dep[d];
t2.modify(rt2[v], 1, 6e5, dis + n, 1);
t2.modify(rt2[d], 1, 6e5, dis + n, -1); //d写成fa[d][0]就相当于把lca的贡献加了两次,可能会错!!!
}