题解：P1600 [NOIP2016 提高组] 天天爱跑步

· · 题解

做法：线段树合并。

对于每一条路径 (s, t)，考虑这条路径上的点 x 能否观测到这条路线上的玩家。

记 s, t 的最近公共祖先为 \rm lca。把路径分为两段，s \to \rm lca 和 \textrm{lca} \to t，分别考虑在这两段上的 x。

当 x 在 s \to \rm lca 上时：

玩家从 s 出发的，每秒走 1 条边，而 x 在 w_x 秒时开始观测，也就是说当 s 和 x 的距离恰好等于 w_x 时，x 可以观测到这名玩家。

由于 x 是 s 的祖先，所以这里计算距离可以用深度作差快速计算。

记 \textrm{dep}_i 为 i 的深度，则 s 和 x 的距离就是 \textrm{dep}_s - \textrm{dep}_x。

此时 x 能观测到玩家当且仅当 \textrm{dep}_s - \textrm{dep}_x = w_x。移项得 \textrm{dep}_s = \textrm{dep}_x + w_x。

当 x 在 \textrm{lca} \to t 上时：

同理可得 s 到 x 的距离是 \textrm{dep}_s - \textrm{dep}_{\textrm{lca}} + \textrm{dep}_x - \textrm{dep}_{\textrm{lca}}。

所以此时 x 能观测到玩家当且仅当 \textrm{dep}_s + \textrm{dep}_x - 2\textrm{dep}_{\textrm{lca}} = w_x。移项得 2\textrm{dep}_{\textrm{lca}} - \textrm{dep}_s = \textrm{dep}_x - w_x。

第一段，每个节点开一棵权值线段树，往 s\to\rm lca 上每个节点的线段树 \textrm{dep}_s 的位置 +1，查询的时候就查 \textrm{dep}_x + w_x 对应的值即可。

第二段同理，再开一棵权值线段树，往 \textrm{lca} \to t 上每个节点的线段树 2\textrm{dep}_{\textrm{lca}} - \textrm{dep}_s 的位置 +1，查询的时候就查 \textrm{dep}_x - w_x 对应的值即可。

链修改用树上差分转为单点修改子树求和，用线段树合并实现，离线处理，把子树处理完后把子树信息全部合并到当前的根，再查询答案。实现部分并不是本题解的重点，参考 P4556 雨天的尾巴。

实现上注意的细节：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

const int N = 3e5 + 5;

int n, m;

int w[N];

vector<int> g[N];

int son[N], siz[N], top[N], dep[N], fa[N];

void dfs1(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    siz[u] = 1;
    for (auto v: g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])
            son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (auto v: g[u])
        if (!top[v])
            dfs2(v, v);
}
int lca(int x, int y) {
    while (top[x] != top[y])
        dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
    return dep[x] < dep[y] ? x : y;
}

int ls[N * 50], rs[N * 50], sum[N * 50], root[N][2], idx;
void modify(int &p, int l, int r, int x, int v) {
    if (!p) p = ++idx;
    sum[p] += v;
    if (l == r) return;
    int mid = l + r >> 1;
    x <= mid ? modify(ls[p], l, mid, x, v) : modify(rs[p], mid + 1, r, x, v);
}
int query(int p, int l, int r, int x) {
    if (!p) return 0;
    if (l == r) return sum[p];
    int mid = l + r >> 1;
    return x <= mid ? query(ls[p], l, mid, x) : query(rs[p], mid + 1, r, x);
}
int merge(int x, int y, int l, int r) {
    if (!x || !y) return x + y;
    if (l == r) {sum[x] += sum[y]; return x;}
    int mid = l + r >> 1;
    ls[x] = merge(ls[x], ls[y], l, mid);
    rs[x] = merge(rs[x], rs[y], mid + 1, r);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    return x;
}

int ans[N];

void dfs(int u, int f) {
    for (auto v: g[u]) {
        if (v == f) continue;
        dfs(v, u);
        root[u][0] = merge(root[u][0], root[v][0], 1, n);
        root[u][1] = merge(root[u][1], root[v][1], -n, 2 * n);
    }
    ans[u] = (dep[u] + w[u] > n ? 0 : query(root[u][0], 1, n, dep[u] + w[u])) + query(root[u][1], -n, 2 * n, dep[u] - w[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;

    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    for (int i = 1; i <= n; i++) cin >> w[i];

    dfs1(1, 0), dfs2(1, 1);

    for (int i = 1, s, t; i <= m; i++) {
        cin >> s >> t;
        int lc = lca(s, t);
        modify(root[s][0], 1, n, dep[s], 1);
        modify(root[lc][0], 1, n, dep[s], -1);
        modify(root[t][1], -n, 2 * n, 2 * dep[lc] - dep[s], 1);
        modify(root[fa[lc]][1], -n, 2 * n, 2 * dep[lc] - dep[s], -1);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";

    return 0;
}