2025勰码公益营 B 班 37号 作业 1-2

· · 个人记录

P1600 [NOIP 2016 提高组] 天天爱跑步 题解

题目大意

给定 n 个节点的树，m 个人分别走 m 个路径，从时刻 0 开始走，1\text{s} 走一条边，询问对于每个点 i，在时刻 w_i 有多少个人在点 i 上。

思路

如果我们对于每个路径求点对他们的贡献，那么要么 \text{TLE}（暴力），要么 \text{MLE}（树剖+二维树状数组）。所以我们考虑拆贡献，对于点求路径对它的贡献。

对于一个点，w_i 上面有人有两种情况：

  1. 那个人还没到达 lca。
  2. 那个人已经到达 lca。

第一种情况

从 a 经过 i 走到 lca，什么时候在点 i 呢？也就是走了 w_i 秒时，又因为此时深度一直减少，所以 a 与 i 的深度相差 w_i。\ 也就是说，当 deep_i + w_i = deep_a 时，路径对 $i

第二种情况

从 lca 经过 i 走到 b，什么时候在点 i 呢？也就是走了 w_i - \text{dis}(a, lca) 秒时，又因为此时深度一直增加，所以 i 与 lca 的深度相差 w_i - \text{dis}(a, lca)。\ 也就是说，当 deep_i = deep_{lca} + w_i - \text{dis}(a, lca)，即 deep_i - w_i = -depp_a + 2 \times depp_{lca} 时，路径对 $i

由于这个问题是离线的，我们考虑树上差分，对于每个路径，我们打四个标记：

我们开一个全局桶，跑 dfs，每个点的子树中对应标记变化量即为答案。

实现&细节

Code

代码中我两种情况分开写了，其实可以一块写。

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

constexpr int maxn = 300010;

int n, m, a, b, w[maxn], ans[maxn];
map <int, int> t; // 这题开到 3e7 都 RE, 改成 map 就好了，不知道为啥
vector <int> G[maxn];
vector <pair <int, int> > tag1[maxn], tag2[maxn];

struct shupou { // 树剖求 LCA
    int r, depp[maxn], fa[maxn], hs[maxn], sz[maxn], lu[maxn], listt[maxn], ll[maxn], li;
    void init(int root) {
        r = root;
        depp[r] = 1;
        lu[r] = r;
        dfs1(r);
        dfs2(r);
        return ;
    }
    void dfs1(int u) {
        sz[u] = 1;
        int maxx = 0;
        for (int i = 0; i < G[u].size(); i++) {
            int now = G[u][i];
            if (now == fa[u]) continue;
            fa[now] = u;
            depp[now] = depp[u] + 1;
            dfs1(now);
            sz[u] += sz[now];
            if (sz[now] > maxx) hs[u] = now, maxx = sz[now];
        }
        return ;
    }
    void dfs2(int u) {
        listt[++li] = u;
        ll[u] = li;
        if (hs[u]) {
            lu[hs[u]] = lu[u];
            dfs2(hs[u]);
        }
        for (int i = 0; i < G[u].size(); i++) {
            int now = G[u][i];
            if (now == fa[u] || now == hs[u]) continue;
            lu[now] = now;
            dfs2(now);
        }
        return ;
    }
    int LCA(int x, int y) {
        if (lu[x] == lu[y]) {
            if (depp[x] > depp[y]) swap(x, y);
            return x;
        }
        if (depp[lu[x]] < depp[lu[y]]) swap(x, y);
        return LCA(fa[lu[x]], y);
    }
} sp;

void dfs1(int u) { // 统计从起点到 lca 的答案
    int lastt = t[sp.depp[u] + w[u]];
    for (pair <int, int> now : tag1[u]) {
        t[now.first] += now.second;
    }
    for (int now : G[u]) {
        if (now == sp.fa[u]) continue;
        dfs1(now);
    }
    ans[u] += t[sp.depp[u] + w[u]] - lastt;
    return ;
}
void dfs2(int u) { // 统计从 lca 到终点的答案
    int lastt = t[sp.depp[u] - w[u]];
    for (pair <int, int> now : tag2[u]) {
        t[now.first] += now.second;
    }
    for (int now : G[u]) {
        if (now == sp.fa[u]) continue;
        dfs2(now);
    }
    ans[u] += t[sp.depp[u] - w[u]] - lastt;
    return ;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }

    sp.init(1);
    for (int i = 1, lca; i <= m; i++) {
        cin >> a >> b;
        lca = sp.LCA(a, b);
        if (sp.depp[a] - sp.depp[lca] == w[lca]) ans[lca]--; // 特判：如果 lca 可以检测到，那么在下面的程序里会被通统计两次，所以在这里减掉一次
        tag1[sp.fa[lca]].push_back({sp.depp[a], -1});
        tag1[a].push_back({sp.depp[a], 1});
        tag2[sp.fa[lca]].push_back({-sp.depp[a] + 2 * sp.depp[lca], -1});
        tag2[b].push_back({-sp.depp[a] + 2 * sp.depp[lca], 1}); // 打标记
    }
    dfs1(1);
    dfs2(1); // 统计答案

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }

    return 0;
}