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

· · 题解

题意简化

一棵树上有 m 个玩家从起点 s_i 跑到终点 t_i，每个节点 j 的观察员在 w_j 秒出现，求每个观察员能看到的玩家数量。

基本思路：LCA+树上差分

我们将第 i 条路径 s_i \rightarrow t_i 分解为 s_i \rightarrow \text{LCA}(s_i, t_i) 和 \text{LCA}(s_i, t_i) \rightarrow t_i，便于求解。

求解路径 1

对于 s_i \rightarrow \text{LCA}(s_i, t_i) 的路径，玩家 i 在节点 u 能被观察到当且仅当 dep_{s_i} - dep_u = w_u。

移项得 dep_{s_i} = w_u + dep_u，相当于路径上每个节点加一个 dep_{s_i} 的值，统计每一个节点 u 上 w_u + dep_u 的数量。

记 cnt_{0, w_u + dep_u} 为这个值的数量，我们在端点 s_i 和 \text{LCA}(s_i, t_i) 处树上差分一个 dep_{s_i} 的值，dfs 遍历整棵树，每访问到一个节点 u，先记录先前的 cnt_{0, w_u + dep_u} 的值，再统计 u 端点处对答案的贡献，统计后的 cnt_{0, w_u + dep_u} 减去先前的值就是节点 u 的答案。

求解路径 2

对于 \text{LCA}(s_i, t_i) \rightarrow t_i 的路径，玩家 i 在节点 u 能被观察到当且仅当 dep_{s_i} + dep_u - 2 \times dep_{\text{LCA}(s_i, t_i)} = w_u。

移项得 dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)} = w_u - dep_u，相当于路径上每一个节点加一个 dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)} 的值，统计每一个节点 u 上 w_u - dep_u 的数量。

记 cnt_{1, w_u - dep_u} 为这个值的数量，我们在端点 s_i 和 \text{LCA}(s_i, t_i) 处树上差分一个 dep_{s_i} - 2 \times dep_{\text{LCA}(s_i, t_i)} 的值，dfs 遍历整棵树，每访问到一个节点 u，先记录先前的 cnt_{1, w_u - dep_u} 的值，再统计 u 端点处对答案的贡献，统计后的 cnt_{1, w_u - dep_u} 减去先前的值就是节点 u 的答案。

AC Code

/*
起点 s 终点 t
对于左路径上的点 x
dep[s]-dep[x]==w[x] => dep[s]==w[x]+dep[x]
对于右路径上的点 y
dep[s]+dep[y]-2*dep[lca(s,y)]==w[y] => dep[s]-2*dep[lca(s,y)]==w[y]-dep[y]
*/
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define pii pair <int, int>
#define mkpr make_pair
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 5, D = 3e5;
int n, m, w[N], d[N], f[N][25], c[2][N<<1], ans[N], dep[N];
vector <int> g[N];
vector <pii> add[N], del[N];
struct path {int u, v;} p[N];
void Dfs(int u, int p) {
    f[u][0] = p;
    dep[u] = dep[p] + 1;
    for (int v : g[u]) {
        if (v == p) continue ;
        Dfs(v, u);
    }
}
void InitLCA() {
    for (int j = 1; j <= 21; j++) {
        for (int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 21; i >= 0; i--) if (dep[f[u][i]] >= dep[v]) u = f[u][i];
    if (u == v) return u;
    for (int i = 21; i >= 0; i--) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}
void Dfs2(int u) {
    int pre1 = c[0][w[u]+dep[u]+D], pre2 = c[1][w[u]-dep[u]+D]; // 计算先前答案
    for (pii cur : add[u]) ++c[cur.fi][cur.se+D];
    for (pii cur : del[u]) --c[cur.fi][cur.se+D];
    for (int v : g[u]) {
        if (v == f[u][0]) continue ;
        Dfs2(v);
    }
    ans[u] = c[0][w[u]+dep[u]+D] - pre1 + c[1][w[u]-dep[u]+D] - pre2;
}
void Solve() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    for (int i = 1; i <= n; i++) cin >> w[i];
    Dfs(1, 0); InitLCA();
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        int lc = LCA(u, v);
        add[u].pb(mkpr(0, dep[u])), del[f[lc][0]].pb(mkpr(0, dep[u]));
        add[v].pb(mkpr(1, dep[u]-2*dep[lc])), del[lc].pb(mkpr(1, dep[u]-2*dep[lc]));
    }
    Dfs2(1);
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Solve();
    return 0;
}