题解-luogu-p1600天天爱跑步(Beta)

题目链接

$n$个点的树上有$m$条路径$(S_i, T_i)$，每条路径上各有一个人从$S_i$跑到$T_i$。他们在第$0$时刻同时跑，每秒能跑一条边。回答$n$个询问，询问恰好在第$W_i$时刻到达节点$i$的人数。

$1 \le n \le 300000,1 \le m \le 300000 $

感谢@tth37 的贡献

准备写一篇较为详细的题解。部分思路来自《算法竞赛进阶指南》。

游戏地图构成树形结构，为方便处理，可以取$1$号节点作为根，转化为有根树处理。

可以发现，从S到T的路径有且只有一条，并且必将经过$lca(S,T)$。

不妨设$x$节点上有一名观察员，其观察时间为$W[x]$。我们可以对$x$的位置进行分情况讨论。

$x$在$S$到$lca(S,T)$的路径上（该路径包含$lca(S,T)$）。

为方便说明，假设$S=6$，$T=4$。那么，此时$x$可能为$1$，$3$或$6$。如果此观察员可以观察到当前玩家，当且仅当$W[x]=d[S]-d[x]$（$d$数组表示节点深度）。对上式移项，得到$W[x]+d[x]=d[S]$。

接下来，我们给每一个节点分配若干个权值，即在每一个节点上开一个一维数组，记录各个权值。根据上式，我们可以将$S$到$lca(S,T)$的路径上每一个节点的$d[S]$号权值加一。按照这种方式处理完所有玩家的信息之后，我们遍历所有节点，每个节点上的$(W[x]+d[x])$号权值即为所求。

该方法的正确性应该不难理解。$(W[x]+d[x])$号权值的意义即为该节点上满足前文所述等式的玩家个数，而满足等式意味着玩家将会在观察员探头时经过观察点，符合题意。

但是这种暴力方法显然还有优化的空间。在有根树的一条链上进行权值更改，可以尝试用树上差分的知识解决。在节点$S$上的$d[S]$号权值加一，节点$fa[lca(S,T)]$上的$d[S]$号权值减一（可以在每个节点上开一个不定长数组vector记录当前节点上的加减操作），最后进行统计时，计算当前子树所有$(W[x]+d[x])$号权值和即可。但即便如此，答案统计也并不容易实现；我们可以使用以下方法：

建立全局数组$s$，其中$s[i]$表示$i$号权值之和。深度优先遍历所有节点，在刚访问到当前节点时，记录$cnt=s[W[x]+d[x]]$。遍历当前节点上的vector，执行加减操作（例如：vector中的一项操作把$3$号权值减一，则$s[3]=s[3]-1$）。递归访问当前节点的所有子节点。访问结束后，$(s[W[x]+d[x]]-cnt)$即为所求。

结合dfs序的相关知识，访问完当前节点的所有子节点之后，$s$数组已经记录了以$x$为根的子树上所有操作。因此将访问后与访问前的权值相减，即为树上差分所得到的答案。

别忘了才分类讨论了一半呢……
$x$在$lca(S,T)$到$T$的路径上（该路径不包含$lca(S,T)$）。

同样假设$S=6$，$T=4$。此时$x$可能为$2$或$4$。如果此观察员可以观察到当前玩家，当且仅当$W[x]=(d[S]-d[lca(S,T)])+(d[x]-d[lca(S,T)])$。对上式移项，得到$W[x]-d[x]=d[S]-2*d[lca(S,T)]$。

类似地，我们只需将操作改为对$(d[S]-2*d[lca(S,T)])$号权值的操作即可。由于权值有可能为负，需要将序号整体平移$N$个单位，即改为对$(d[S]-2*d[lca(S,T)]+N)$号权值的操作。在每个节点上另开一个操作vector，统计答案时另开一个$s$数组，将计算出的答案与第一种情况的答案相加即可。

Q：为什么必须另开操作vector和$s$数组？

A：回顾一下提到的两个式子：$W[x]+d[x]=d[S]$，$W[x]-d[x]=d[S]-2*d[lca(S,T)]$如果将两者合起来操作，有可能产生“将$d[S]$号权值加一，碰巧统计答案时$W[x]-d[x]=d[S]$”的情况。然而，上述等式是没有任何意义的：$x$号节点根本无法观察到玩家。为了避免此类错误，必须将两种操作分开处理。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

struct opt {int id, op;};
vector<int> G[MAXN];
vector<opt> opt1[MAXN], opt2[MAXN];
int N, M;
int W[MAXN];
int f[MAXN][20], d[MAXN];

void dfs1(int u, int fa) {
    f[u][0] = fa, d[u] = d[fa] + 1;
    for (register int i = 1; i <= 19; ++i)
        f[u][i] = f[f[u][i-1]][i-1];
    for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = *it;
        if (v == fa) continue;
        dfs1(v, u);
    }
}

inline int Lca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    for (register int i = 19; i >= 0; --i) {
        if (d[f[u][i]] >= d[v]) u = f[u][i];
    }
    if (u == v) return u;
    for (register int i = 19; i >= 0; --i) {
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}

int s1[MAXN*3], s2[MAXN*3];
int ans[MAXN];

void dfs2(int u, int fa) {
    int cnt1 = s1[W[u] + d[u] + N];
    int cnt2 = s2[W[u] - d[u] + N];
    for (vector<opt>::iterator it = opt1[u].begin(); it != opt1[u].end(); it++)
        s1[it->id] += it->op;
    for (vector<opt>::iterator it = opt2[u].begin(); it != opt2[u].end(); it++)
        s2[it->id] += it->op;
    for (vector<int>::iterator it = G[u].begin(); it != G[u].end(); it++) {
        int v = *it;
        if (v == fa) continue;
        dfs2(v, u);
    }
    ans[u] = s1[W[u] + d[u] + N] - cnt1 + s2[W[u] - d[u] + N] - cnt2;
}

int main() {
    scanf("%d%d", &N, &M);
    for (register int i = 1; i < N; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs1(1, 0);
    for (register int i = 1; i <= N; ++i)
        scanf("%d", &W[i]);
    for (register int i = 1; i <= M; ++i) {
        int S, T;
        scanf("%d%d", &S, &T);
        int lca = Lca(S, T);
        opt1[S].push_back((opt){d[S] + N, 1});
        opt1[f[lca][0]].push_back((opt){d[S] + N, -1});
        opt2[T].push_back((opt){d[S] - 2*d[lca] + N, 1});
        opt2[lca].push_back((opt){d[S] - 2*d[lca] + N, -1});
    }
    dfs2(1, 0);
    for (register int i = 1; i <= N; ++i)
        printf("%d ", ans[i]);
    return 0;
}

# 最近公共祖先, 树上差分

题解-luogu-p1600天天爱跑步(Beta)

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!