题目链接：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;
}
2 条评论
OωO
%%%