警,示,后,人
查看原帖
警,示,后,人
483928
Z1qqurat楼主2023/8/28 20:44

如果你也和我一样,那这件事情就是说把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的贡献加了两次,可能会错!!!
    }
2023/8/28 20:44
加载中...