题目链接:LOJ 2322

不远的一年前,小 V 还是一名清华集训的选手,坐在机房里为他已如风中残烛的OI生涯做最后的挣扎。而如今,他已成为了一名光荣的出题人。他感到非常激动,不禁感叹道:“Hello world!”。

小 V 有 $n$ 道题,他的题都非常毒瘤,所以关爱选手的 ufozgg 打算削弱这些题。为了逃避削弱,小 V 把他的毒瘤题都藏到了一棵 $n$ 个节点的树里(节点编号从 $1$ 至 $n$),这棵树上的所有节点与小 V 的所有题一一对应。小 V 的每一道题都有一个毒瘤值,节点 $i$ (表示标号为 $i$ 的树上节点,下同)对应的题的毒瘤值为 $a_i$ 。

魔法师小 V 为了保护他的题目,对这棵树施了魔法,这样一来,任何人想要一探这棵树的究竟,都必须在上面做跳跃操作。每一次跳跃操作包含一个起点 $s$ 、一个终点 $t$ 和一个步频 $k$ ,这表示跳跃者会从 $s$ 出发,在树上沿着简单路径多次跳跃到达 $t$ ,每次跳跃,如果从当前点到 $t$ 的最短路长度不超过 $k$ ,那么跳跃者就会直接跳到 $t$ ,否则跳跃者就会沿着最短路跳过恰好 $k$ 条边。

既然小 V 把题藏在了树里,ufozgg 就不能直接削弱题目了。他就必须在树上跳跃,边跳跃边削弱题目。ufozgg 每次跳跃经过一个节点(包括起点 $s$ ,当 $s=t$ 的时候也是如此),就会把该节点上的题目的毒瘤值开根并向下取整:即如果他经过了节点 $i$,他就会使 $a_i = \lfloor\sqrt a_i \rfloor$。这种操作我们称为削弱操作

ufozgg 还会不时地希望知道他对题目的削弱程度。因此,他在一些跳跃操作中会放弃对题目的削弱,转而统计该次跳跃经过节点的题目毒瘤值总和。这种操作我们称为统计操作

吃瓜群众绿绿对小 V 的毒瘤题和 ufozgg 的削弱计划常感兴趣。他现在想知道 ufozgg 每次做统计操作时得到的结果。你能帮帮他吗?

数据范围:$1 \le n \le 5 \times 10 ^ 4$,$1 \le Q \le 4 \times 10 ^ 5$,$1 \le a_i \le 10 ^ {13}$。


Solution

对于每个数字,最多开根 $\log \log$ 次就会变成 $1$。因此开根次数不会超过 $6$ 次。

对于较大的 $k$,涉及的节点数量是不多的,考虑对 $k$ 按照 $\alpha$ 分块。

  • 对于 $> \alpha$ 的 $k$:在树上暴力跳节点。
  • 对于 $\le \alpha$ 的 $k$:对于修改操作,记 $f(i, j)$ 表示节点 $i$ 向上 $j$ 整数倍距离($0, j, 2j, \ldots$ 等等)的节点中,最深的权值大于 $1$ 节点。每次在并查集上往上跳,一旦当前点被修改为 $1$ 后就更新改点的并查集;对于查询操作,建立 $\alpha$ 棵树状数组,第 $i$ 棵统计深度 $k = i$ 的节点的权值(具体地,我们只要使深度 $\bmod i$ 相同的节点的 $\text{dfs}$ 序连续即可)。

总的时间复杂度为 $\mathcal O(Q\frac{n}{\alpha} + 6n \log n \alpha)$,由于并查集等的大常数,$\alpha$ 取 $20$ 左右效果较好。

时间复杂度:$\mathcal O(Q\frac{n}{\alpha} + 6n \log n \alpha)$。


Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 5e4, M = 20, LogN = 15;
int n, q, lg[N + 5], bel[M + 1][N + 5];
int dep[N + 5], len[N + 5], son[N + 5], top[N + 5], father[LogN + 1][N + 5];
int dfn[M + 1][N + 5], end[M + 1][N + 5], dfc[M + 1];
int64 a[N + 5];
std::vector<int> E[N + 5], dw[N + 5], up[N + 5];
struct Fenwick {
    int64 a[N + 5];
    inline void modify(int x, int64 w) {
        for (; x <= n; x += x & -x) {
            a[x] += w;
        }
    }
    inline int64 query(int x) {
        int64 ans = 0;
        for (; x > 0; x ^= x & -x) {
            ans += a[x];
        }
        return ans;
    }
    inline void modify(int l, int r, int64 w) {
        modify(l, w);
        modify(r + 1, -w);
    }
} T[M + 1];

void init() {
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
}
void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    father[0][u] = p;
    for (int i = 1; i <= lg[n]; i++) {
        father[i][u] = father[i - 1][father[i - 1][u]];
    }
    for (auto v : E[u]) {
        if (v != p) {
            dfs1(v, u);
            len[u] = std::max(len[u], len[v] + 1);
            if (son[u] == 0 || len[v] > len[son[u]]) {
                son[u] = v;
            }
        }
    }
}
void dfs2(int u, int p, int from) {
    top[u] = from;
    if (from == u) {
        for (int t = u, i = 0; i <= len[u]; i++) {
            dw[u].push_back(t);
            t = son[t];
        }
        for (int t = u, i = 0; t > 0 && i <= len[u]; i++) {
            up[u].push_back(t);
            t = father[0][t];
        }
    }
    if (son[u]) {
        dfs2(son[u], u, from);
    }
    for (auto v : E[u]) {
        if (v != p && v != son[u]) {
            dfs2(v, u, v);
        }
    }
}
void dfs3(int u, int p, int k) {
    int c = dep[u] % k;
    dfn[k][u] = ++dfc[c];
    for (auto v : E[u]) {
        if (v != p) {
            dfs3(v, u, k);
        }
    }
    end[k][u] = dfc[c];
}
int find(int x, int k) {
    return bel[k][x] == x ? x : bel[k][x] = find(bel[k][x], k);
}
inline int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        std::swap(u, v);
    }
    int dif = dep[u] - dep[v];
    for (int i = lg[dif]; i >= 0; i--) {
        if ((dif >> i) & 1) {
            u = father[i][u];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = lg[dep[u]]; i >= 0; i--) {
        if (father[i][u] != father[i][v]) {
            u = father[i][u];
            v = father[i][v];
        }
    }
    return father[0][u];
}
inline int ancestor(int u, int k) {
    if (k == 0) {
        return u;
    }
    if (dep[u] <= k) {
        return 0;
    }
    int r = lg[k];
    u = father[r][u];
    k -= 1 << r;
    int d = dep[u] - dep[top[u]];
    return k <= d ? dw[top[u]][d - k] : up[top[u]][k - d];
}
inline void fix(int u) {
    for (int i = 1, p = father[0][u]; p > 0 && i <= M; i++, p = father[0][p]) {
        bel[i][u] = find(p, i);
    }
}
inline void modify(int u) {
    if (a[u] == 1) {
        return;
    }
    int64 _a = sqrt(a[u]), delta = _a - a[u];
    for (int i = 1; i <= M; i++) {
        T[i].modify(dfn[i][u], end[i][u], delta);
    }
    if ((a[u] = _a) == 1) {
        fix(u);
    }
}
inline void modify(int u, int v, int k) {
    int x = lca(u, v), dis = dep[u] + dep[v] - dep[x] * 2;
    if (dis % k) {
        modify(v);
        v = ancestor(v, dis % k);
    }
    if (k <= M) {
        u = find(u, k);
        for (; dep[u] >= dep[x]; ) {
            modify(u);
            u = find(ancestor(u, k), k);
        }
        v = find(v, k);
        for (; dep[v] > dep[x]; ) {
            modify(v);
            v = find(ancestor(v, k), k);
        }
    } else {
        for (; dep[u] >= dep[x]; ) {
            modify(u);
            u = ancestor(u, k);
        }
        for (; dep[v] > dep[x]; ) {
            modify(v);
            v = ancestor(v, k);
        }
    }
}
inline void query(int u, int v, int k) {
    int x = lca(u, v), dis = dep[u] + dep[v] - dep[x] * 2;
    int64 ans = 0;
    if (dis % k) {
        ans = a[v];
        v = ancestor(v, dis % k);
    }
    if (k <= M) {
        int t = (dep[u] - dep[x]) / k + 1;
        ans += T[k].query(dfn[k][u]) - T[k].query(dfn[k][ancestor(u, t * k)]);
        t = dep[v] <= dep[x] ? 0 : (dep[v] - dep[x] - 1) / k + 1;
        ans += T[k].query(dfn[k][v]) - T[k].query(dfn[k][ancestor(v, t * k)]);
    } else {
        for (; dep[u] >= dep[x]; ) {
            ans += a[u];
            u = ancestor(u, k);
        }
        for (; dep[v] > dep[x]; ) {
            ans += a[v];
            v = ancestor(v, k);
        }
    }
    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for (int k = 1; k <= M; k++) {
        std::vector<int> cnt(k, 0);
        for (int i = 1; i <= n; i++) {
            cnt[dep[i] % k]++;
        }
        std::partial_sum(cnt.begin(), cnt.end(), cnt.begin());
        dfc[0] = 0;
        for (int i = 1; i < k; i++) {
            dfc[i] = cnt[i - 1];
        }
        dfs3(1, 0, k);
        for (int i = 1; i <= n; i++) {
            bel[k][i] = i;
            T[k].modify(dfn[k][i], end[k][i], a[i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            fix(i);
        }
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int opt, u, v, k;
        scanf("%d%d%d%d", &opt, &u, &v, &k);
        opt == 0 ? modify(u, v, k) : query(u, v, k);
    }
    return 0;
}
最后修改:2020 年 12 月 22 日 07 : 55 AM