题目链接： NOIP2016 提高组] 天天爱跑步

这道题搁了好久了没写，今天浅录一下

题意

小c制作了一款叫做《天天爱跑步》的游戏。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n-1$ 条边的树，每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$，终点为 $t_i$。每天打卡任务开始时，所有玩家在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树，所以每个人的路径是唯一的)

小c 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 $j$ 的观察员会选择在第 $w_j$ 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 $w_j$ 秒也正好到达了结点 $j$ 。小c 想知道每个观察员会观察到多少人?

思路

我们将$s \rightarrow t$的路径分成$s \rightarrow lca$和$lca \rightarrow t$这两条路径，前者深度递减，我们称它为上升链，后者深度递增，我们称之为下降链。

这里放张图。

graph

假设当前的$s=3,t=5$那么他们的$lca=1$。

首先我们分析上升链，处于该链上的节点若想要观察到该玩家，那么必须满足
$$
w_x = depth_s - depth_x
$$
即
$$
depth_x + w_x = depth_s
$$
然后我们在这条上升链上差分一下，在$s$处插入$1$个$depth_s$，在$fa_{lca}$处插入$-1$个$depth_s$

接下来分析下降链，还是一样先计算类似上升链的等式
$$
w_x = depth_x - depth_{lca} + depth_s - depth_{lca}
$$
即
$$
depth_x - w_x = 2 \times depth_{lca} - depth_s
$$
然后我们在除去$lca$的下降链上进行差分($lca$已经包含在上升链内)，在$t$处插入$1$个$2 \times depth_{lca} - depth_s$，在$lca$出插入$-1$个$2 \times depth_{lca} - depth_s$

最后我们再$dfs$统计一下，将每个子树的信息合并到该子树的根节点上，然后分别查询$depth_x+w_x$以及$depth_x-w_x$的出现次数，最后加起来就为观察员$x$在$w_x$时刻能够观察到的玩家个数。

需要注意的是若$w_x=0$，上升和下降会重复计算一次，需要特判一下。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 3e5 + 5, MOD = 998244353, INF = 0x3f3f3f3f;

int n, m, w[N];
vector< int > adj[N];
int dep[N], top[N], son[N], siz[N], f[N];
void dfs1(int x, int p) {
    dep[x] = dep[p] + 1;
    siz[x] = 1;
    f[x] = p;
    for (const auto &y : adj[x]) {
        if (y ^ p) {
            dfs1(y, x);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    }
}
void dfs2(int x, int tp) {
    top[x] = tp;
    if (!son[x]) {
        return;
    }
    dfs2(son[x], tp);
    for (const auto &y : adj[x]) {
        if (y != son[x] && y != f[x]) {
            dfs2(y, y);
        }
    }
}
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        x = f[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}
int rt[N], ls[N << 6], rs[N << 6], cnt[N << 6], tot;
void Modify(int &x, int l, int r, int p, int k) {
    if (!x) {
        x = ++ tot;
    }
    if (l == r) {
        cnt[x] += k;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
        Modify(ls[x], l, mid, p, k);
    } else {
        Modify(rs[x], mid + 1, r, p, k);
    }
}
int Merge(int x, int y, int l, int r) {
    if (!x || !y) {
        return x | y;
    }
    int z = ++ tot;
    if (l == r) {
        cnt[z] = cnt[x] + cnt[y];
    } else {
        int mid = (l + r) >> 1;
        ls[z] = Merge(ls[x], ls[y], l, mid);
        rs[z] = Merge(rs[x], rs[y], mid + 1, r);
    }
    return z;
}
int Query(int x, int l, int r, int p) {
    if (!x) {
        return 0;
    }
    if (l == r) {
        return cnt[x];
    }
    int mid = (l + r) >> 1;
    if (p <= mid) {
        return Query(ls[x], l, mid, p);
    }
    return Query(rs[x], mid + 1, r, p);
}
int ans[N];
void dfs(int x, int p) {
    for (const auto &y : adj[x]) {
        if (y ^ p) {
            dfs(y, x);
            rt[x] = Merge(rt[x], rt[y], -n, n);
        }
    }
    if (dep[x] + w[x] <= n) {
        ans[x] += Query(rt[x], -n, n, dep[x] + w[x]);
    }
    if (dep[x] - w[x] >= -n) {
        ans[x] += Query(rt[x], -n, n, dep[x] - w[x]);
    }
    if (!w[x]) {
        ans[x] >>= 1;
    }
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i < n; ++ i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> w[i];
    }
    while (m -- ) {
        int s, t;
        cin >> s >> t;
        int kk = lca(s, t);
        Modify(rt[s], -n, n, dep[s], 1);
        Modify(rt[f[kk]], -n, n, dep[s], -1);
        Modify(rt[t], -n, n, 2 * dep[kk] - dep[s], 1);
        Modify(rt[kk], -n, n, 2 * dep[kk] - dep[s], -1);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++ i) {
        cout << ans[i] << " \n"[i == n];
    }
    return 0;
}