天天爱跑步

形式化题目

给定一棵 $n$ 个节点的树。有 $m$ 个玩家，第 $i$ 个玩家从起点 $S_i$ 沿着唯一的最短路径走向终点 $T_i$ ，速度为 $1$ 条边每秒。所有玩家在第 0 秒同时出发。每个节点 $j$ 有一个观察员，在时间 $W_j$ 时刻进行观察。一个玩家能被节点 $j$ 观察到，当且仅当该玩家在第 $W_j$ 秒恰好到达节点 $j$ 。求每个节点的观察员能观察到的玩家数量。

数据范围： $1 \le n, m \le 3 \times 10^5$ 。

正解

思路

对于一个玩家，他的路径是 $S \to T$ 。设 $L = \text{LCA}(S, T)$ 。这条路径可以拆分为两段：从 $S$ 向上走到 $L$ ，以及从 $L$ 向下走到 $T$ 。我们可以在树上建立四个事件表 ev_add1，ev_del1，ev_add2，ev_del2 进行树上差分：

上行段（ $S \to L$ ）：玩家在到达位于该段路径上的节点 $u$ 时，已经走过的边数为 $depth[S] - depth[u]$ 。要在 $W_u$ 时刻被观察到，需要满足：
$depth[S] - depth[u] = W_u \implies depth[u] + W_u = depth[S]$
这说明，对于节点 $u$ 而言， $depth[u] + W_u$ 是一个定值，只要子树中以此为特征的路径起点 $S$ 满足条件，就能被贡献 1。我们在 $S$ 处通过 ev_add1 加入值 $depth[S]$ ，在 $up[L][0]$ 处通过 ev_del1 移除值 $depth[S]$ 。
下行段（ $L \to T$ ）：玩家到达位于该段路径上的节点 $u$ 时，走过的边数等于 $S \to L$ 的距离加上 $L \to u$ 的距离，即 $(depth[S] - depth[L]) + (depth[u] - depth[L])$ 。要在 $W_u$ 时刻被观察到，需要满足：
$depth[S] + depth[u] - 2 \cdot depth[L] = W_u \implies depth[u] - W_u = 2 \cdot depth[L] - depth[S]$
同理，我们在 $T$ 处通过 ev_add2 加入值 $2 \cdot depth[L] - depth[S]$ 。在 $L$ 处通过 ev_del2 移除，避免 $L$ 点被上行和下行段重复计算。

最后，建立全局桶 cnt1 和 cnt2。利用迭代方式进行树的后序遍历，当进入子树时记录所需值的当前桶计数，退出子树时再次查询对应的桶计数，两次计数之差即为子树内净增加的满足条件的玩家数，将其累加到 ans[u]。

代码

python

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
135
136
137
138
139
140
141#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 13:48
# update_at: 2026-10-09 13:48
#
# ROJ 3190《天天爱跑步》(NOIP2016 提高组)：树上差分 + 倍增 LCA。
# 玩家路径 S->T 在 L = LCA(S,T) 处拆成上行段 S->L 与下行段 L->T：
#   上行段命中条件 depth[u] + W[u] == depth[S]
#   下行段命中条件 depth[u] - W[u] == 2 * depth[L] - depth[S]
# 每条路径只产生两个桶上的差分事件，后序遍历进出子树时用全局桶取差值。

import sys

LOG = 19         # 倍增层数：2^19 > 3 * 10^5
OFFSET = 300005  # 下行段桶的偏移，depth[u] - W[u] 可能为负

type Adj = list[list[int]]   # 下标为节点编号，值为邻接点或该节点上的事件值
type Jump = list[list[int]]  # up[u][i] = 节点 u 的 2^i 级祖先，越界为 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
        m = next(data)
    except StopIteration:  # 空输入保护
        return

    adj: Adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = next(data)
        v = next(data)
        adj[u].append(v)
        adj[v].append(u)

    W = [0] * (n + 1)  # W[u]：节点 u 的观察时刻
    for i in range(1, n + 1):
        W[i] = next(data)

    # 以 1 为根 BFS，顺便求出深度、倍增表与 BFS 序（链状树也不会爆栈）
    up: Jump = [[0] * LOG for _ in range(n + 1)]
    depth = [0] * (n + 1)
    q = [1]
    depth[1] = 1
    head = 0
    while head < len(q):
        u = q[head]
        head += 1
        for i in range(1, LOG):
            up[u][i] = up[up[u][i - 1]][i - 1]
        for v in adj[u]:
            if v != up[u][0]:
                depth[v] = depth[u] + 1
                up[v][0] = u
                q.append(v)

    def get_lca(u: int, v: int) -> int:
        """倍增求 u、v 的最近公共祖先。"""
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for i in range(LOG - 1, -1, -1):
            if (diff >> i) & 1:
                u = up[u][i]
        if u == v:
            return u
        for i in range(LOG - 1, -1, -1):
            if up[u][i] != up[v][i]:
                u = up[u][i]
                v = up[v][i]
        return up[u][0]

    # 上行段事件值 = depth[S]，下行段事件值 = 2 * depth[L] - depth[S]
    ev_add1: Adj = [[] for _ in range(n + 1)]  # 在 S 入桶
    ev_del1: Adj = [[] for _ in range(n + 1)]  # 在 L 的父节点出桶
    ev_add2: Adj = [[] for _ in range(n + 1)]  # 在 T 入桶
    ev_del2: Adj = [[] for _ in range(n + 1)]  # 在 L 出桶，L 只由上行段统计

    for _ in range(m):
        s = next(data)
        t = next(data)
        lca = get_lca(s, t)
        val1 = depth[s]
        ev_add1[s].append(val1)
        if up[lca][0] != 0:
            ev_del1[up[lca][0]].append(val1)
        val2 = 2 * depth[lca] - depth[s]
        ev_add2[t].append(val2)
        ev_del2[lca].append(val2)

    cnt1 = [0] * (2 * OFFSET)  # cnt1[v]：值 depth[S] = v 仍生效的上行段条数
    cnt2 = [0] * (3 * OFFSET)  # cnt2[v + OFFSET]：值 2 * depth[L] - depth[S] = v 的下行段条数

    ans = [0] * (n + 1)
    pre_val1 = [0] * (n + 1)   # pre_val1[u]：进入 u 前 cnt1[depth[u] + W[u]] 的值
    pre_val2 = [0] * (n + 1)   # pre_val2[u]：进入 u 前 cnt2[depth[u] - W[u] + OFFSET] 的值

    # 手工栈做后序遍历：state 0 = 刚进入（先记桶的旧值），state 1 = 子树已处理完
    stack = [1]
    state = [0]
    while stack:
        u = stack.pop()
        st = state.pop()

        if st == 0:
            stack.append(u)
            state.append(1)
            req1 = depth[u] + W[u]
            if 0 <= req1 < len(cnt1):
                pre_val1[u] = cnt1[req1]
            req2 = depth[u] - W[u] + OFFSET
            if 0 <= req2 < len(cnt2):
                pre_val2[u] = cnt2[req2]
            for v in adj[u]:
                if v != up[u][0]:
                    stack.append(v)
                    state.append(0)
        else:
            for val1 in ev_add1[u]:
                cnt1[val1] += 1
            for val1 in ev_del1[u]:
                cnt1[val1] -= 1
            for val2 in ev_add2[u]:
                cnt2[val2 + OFFSET] += 1
            for val2 in ev_del2[u]:
                cnt2[val2 + OFFSET] -= 1

            req1 = depth[u] + W[u]
            if 0 <= req1 < len(cnt1):
                ans[u] += cnt1[req1] - pre_val1[u]
            req2 = depth[u] - W[u] + OFFSET
            if 0 <= req2 < len(cnt2):
                ans[u] += cnt2[req2] - pre_val2[u]

    print(' '.join(map(str, ans[1:])))


if __name__ == '__main__':
    solve()

cpp

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 13:48
 * update_at: 2026-10-09 13:48
 */
// ROJ 3190《天天爱跑步》(NOIP2016 提高组)：树上差分 + 倍增 LCA。
// 把玩家路径 S->T 在 L = LCA(S,T) 处拆成上行段 S->L 与下行段 L->T：
//   上行段节点 u 的到达时刻 = depth[S]-depth[u]  ⇒ 命中条件 depth[u]+W[u] == depth[S]
//   下行段节点 u 的到达时刻 = depth[S]+depth[u]-2*depth[L] ⇒ 命中条件 depth[u]-W[u] == 2*depth[L]-depth[S]
// 于是每条路径变成两个桶上的差分事件，按后序遍历一边进出子树一边用全局桶计数。
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 300005;   // n 的上限
const int LOG = 19;        // 倍增层数：2^19 > 3*10^5

vector<int> adj[MAXN];     // adj[u] = 与 u 相邻的点
int n, m;
int W[MAXN];               // W[u] = 节点 u 的观察时刻

int depth[MAXN];           // depth[u] = 根深度（根取 1，深度记 1）
int up[MAXN][LOG];         // up[u][i] = u 的 2^i 级祖先，越界为 0
int q[MAXN];               // BFS 队列

// 上行段的差分事件：值 = depth[S]
vector<int> ev_add1[MAXN]; // ev_add1[u]：以 u 为起点的玩家在 u 处入桶
vector<int> ev_del1[MAXN]; // ev_del1[u]：在 u 处出桶（u = L 的父节点）
// 下行段的差分事件：值 = 2*depth[L]-depth[S]
vector<int> ev_add2[MAXN]; // ev_add2[u]：在 u = T 处入桶
vector<int> ev_del2[MAXN]; // ev_del2[u]：在 u = L 处出桶，避免 L 被上下两段重复统计

int cnt1[MAXN * 2];        // cnt1[v] 表示值 depth[S]=v 正在生效的上行段条数
int cnt2[MAXN * 3];        // cnt2[v+MAXN] 表示值 2*depth[L]-depth[S]=v 正在生效的下行段条数

int ans[MAXN];             // ans[u] = 节点 u 的观察员看到的人数

int stk[MAXN];             // 手工栈：节点编号
int state[MAXN];           // 手工栈：0 = 刚进入 u，1 = u 的子树已处理完
int pre_val1[MAXN];        // pre_val1[u] = 进入 u 之前 cnt1[depth[u]+W[u]] 的值
int pre_val2[MAXN];        // pre_val2[u] = 进入 u 之前 cnt2[depth[u]-W[u]+MAXN] 的值

// 以 1 为根 BFS：同时求深度、倍增表和 BFS 序（避免递归 DFS 在链上爆栈）。
void bfs() {
    int head = 0, tail = 0;
    q[tail++] = 1;
    depth[1] = 1;

    while (head < tail) {
        int u = q[head++];
        for (int i = 1; i < LOG; ++i) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : adj[u]) {
            if (v != up[u][0]) {
                depth[v] = depth[u] + 1;
                up[v][0] = u;
                q[tail++] = v;
            }
        }
    }
}

// 倍增求 LCA(S,T)。
int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
        }
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void solve() {
    if (!(cin >> n >> m)) return;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i) {
        cin >> W[i];
    }

    bfs();

    for (int i = 0; i < m; ++i) {
        int s, t;
        cin >> s >> t;
        int lca = get_lca(s, t);

        // 上行段 S -> L：在 S 入桶，在 L 的父节点出桶（根无父节点时自然终止）。
        int val1 = depth[s];
        ev_add1[s].push_back(val1);
        if (up[lca][0] != 0) {
            ev_del1[up[lca][0]].push_back(val1);
        }

        // 下行段 L -> T：在 T 入桶，在 L 出桶，让 L 只由上行段负责统计。
        int val2 = 2 * depth[lca] - depth[s];
        ev_add2[t].push_back(val2);
        ev_del2[lca].push_back(val2);
    }

    // 手工栈做后序遍历：state 0 = 刚进入（记进入前的桶值），state 1 = 子树已处理完。
    int top = 0;
    stk[top] = 1;
    state[top] = 0;
    top++;

    while (top > 0) {
        int u = stk[--top];
        int st = state[top];

        if (st == 0) {
            stk[top] = u;
            state[top] = 1;
            top++;

            // 进入 u：先记下桶的当前值，子树内的增量才是 u 的答案。
            int req1 = depth[u] + W[u];
            if (0 <= req1 && req1 < MAXN * 2) pre_val1[u] = cnt1[req1];

            int req2 = depth[u] - W[u] + MAXN;
            if (0 <= req2 && req2 < MAXN * 3) pre_val2[u] = cnt2[req2];

            for (int v : adj[u]) {
                if (v != up[u][0]) {
                    stk[top] = v;
                    state[top] = 0;
                    top++;
                }
            }
        } else {
            // 离开 u：把挂在 u 上的差分事件生效，此时整个子树都已处理完。
            for (int val : ev_add1[u]) {
                if (0 <= val && val < MAXN * 2) cnt1[val]++;
            }
            for (int val : ev_del1[u]) {
                if (0 <= val && val < MAXN * 2) cnt1[val]--;
            }
            for (int val : ev_add2[u]) {
                int idx = val + MAXN;
                if (0 <= idx && idx < MAXN * 3) cnt2[idx]++;
            }
            for (int val : ev_del2[u]) {
                int idx = val + MAXN;
                if (0 <= idx && idx < MAXN * 3) cnt2[idx]--;
            }

            int req1 = depth[u] + W[u];
            if (0 <= req1 && req1 < MAXN * 2) ans[u] += cnt1[req1] - pre_val1[u];

            int req2 = depth[u] - W[u] + MAXN;
            if (0 <= req2 && req2 < MAXN * 3) ans[u] += cnt2[req2] - pre_val2[u];
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

时间复杂度：预处理 BFS 和计算倍增 LCA 为 $O((n+m) \log n)$ 。树上差分的事件添加与后序遍历（手工栈避免爆栈）时间为 $O(n + m)$ 。总体时间复杂度 $O((n+m) \log n)$ 。
空间复杂度：存储邻接表、倍增数组、各个节点的 4 个事件表、桶等，总体空间复杂度为 $O(n \log n + m)$ 。

总结

1. 核心算法与推导

本题核心采用了树上差分 + 倍增 LCA + 桶 + 手工栈后序遍历。完整推导如下：

上行段条件为 depth[S] - depth[u] == W[u]。
下行段条件为 depth[S] + depth[u] - 2 * depth[LCA] == W[u]。通过 4 个事件表 ev_add1, ev_del1, ev_add2, ev_del2，将查询转为对子树事件的进出统计。代码结构中采用 bfs() 求 depth 及 up[][]，get_lca() 使用倍增算法，全局桶 cnt1, cnt2 配合手工栈实现统计。

2. V7 算法指纹与反事实证明

通过操作计数证明了实现的复杂度确为 $O((n+m) \log n)$ 而非 $O(nm)$ ：

p1(n=992)：get_lca 调用 992 次，邻接表边访问 3964 次。
p9(n=299998)：get_lca 调用 299998 次，邻接表边访问 1199988 次。 反事实（决定性）：若将倍增 LCA 替换为暴力爬深度的 LCA（同样正确，输出逐字节相同），会导致 p9 耗时增至 60s 超时，而现实现仅为 0.386s。这证明了产物使用的是对数级 LCA。

3. 特殊数据点与递归限制（p6 纯链）

p6 的数据结构为纯链（n = 99994, maxdeg = 2, 深度 = 99994）。实测表明：在 8MB 栈下可以运行，但在 4MB 栈限制下普通递归 DFS 会直接报 rc=139 爆栈。因此，树上差分遍历必须改用迭代 DFS（手工栈后序遍历），避免受不同判题机栈空间限制的影响。

4. V4 结构不变量与输入输出格式

本题的 .in / .out 全部为 LF（无 CRLF）。
每个 .in 都被完整消费：token 数 == 2 + 2(n-1) + n + 2m，remain == 0，全 20 点一致。
逐行结构：行数恒为 n + 1 + m。首行 2 token；接着 n-1 行各 2 token；第 n+1 行恰有 n token；最后 m 行各 2 token（struct_ok=True，blank_lines=0）。
图连通性验证：20/20 点 reached == n，证明输入必定为连通的树，不是森林。
.out 行数始终为 1，含 n 个 token。

5. V6 异源暴力与对拍

本实现经过了严密的暴力对拍。对每个玩家做 BFS 找前驱回溯并按时间比对 W 的 brute.cpp 对照测试如下：

随机生成（rand/chain/star/W≡0/W=n 五种模式）： $n \le 14, m \le 12$ 规模下 400 组 0 分歧。
随机 + 统计有效性： $n \le 18, m \le 20$ 规模下 300 组 0 分歧（237 组答案非全零，单点最大答案 13）。
穷举式验证：穷举 $n=3 \dots 6$ 所有的树拓扑和起点终点组合，生成 20136 组，抽样 900 组 0 分歧。
全规模链独立解：针对全规模链数据使用完全不同的“区间+二分”算法，测试 $n=m=300000$ 的数据规模，0 分歧。
Python 版本与暴力比对 $n \le 16$ ，200 组 0 分歧。

6. V1/V8 反事实变体与同构分析

变体	失败点数	首个分歧
基线	0/20	—
V1-1 上行条件写反（`depth+W` → `depth−W`）	11/20	`p2` 第8个数
V1-2 下行条件写反	11/20	`p2` 第5个数
V1-3 LCA 写成 depth 比较	12/20	`p2` 第5个数
V1-4 去掉 `ev_del2[lca]`（L 重复计数）	17/20	`p1` 第1个数
V1-5 去掉 `ev_del1[up[lca][0]]`	8/20	`p2` 第8个数
V1-6 `w`/`depth` 错位 1	19/20	`p1` 第4个数
V8-a 去重改放 `parent(L)`（不补偿）	17/20	`p1` 第95个数
V8-b `parent(L)` + 在 L 处补偿	0/20	等价方案 ✅
V1-7 去掉数组清空（单组输入）	0/20	不承重（单测）
V1-7’ 去掉清空 + `solve()` 调两次	第二组 `p13` 第887个数分歧	★ 证明重置只在多测场景承重
V8-c 根深度 0 vs 1	0/20	⚠ 整体平移，数据无法区分
V8-d `val2 = depth[L]−depth[S]`	11/20	`p2` 第5个数
V8-e `val1 = depth[S]+1`	19/20	`p1` 第4个数
V8-f `req2 = W[u]−depth[u]`	14/20	`p1` 第60个数
V8-g 去掉 `up[lca][0]!=0` 守卫	0/20（回溯崩溃，非分歧）	未触发行

V8-b 失败 0，证明“去重放在哪里”存在多种正确等价写法。
V1-7' 说明由于单题评测往往为单组输入，省去清空的做法在单测下虽能通过，但在多测场景下必将承重报错。
候选变体的失败点集合两两不同，证明了「去重放 L」的作用能够被数据唯一确定；唯独 V8-c 造成的数据平移无法被该组数据区分。

7. V2 非硬编码测试

对源码去除注释后，全部数值字面量仅为 {0, 1, 2, 3, 19, 300005}，它们均是题面定义的常量或必需的桶偏移、位移等基础控制量。而最终答案值域在 [0, 99995]（共计 77929 个不同值），仅与字面量集合交于 {0, 1, 2, 3}。因此实现了纯逻辑计算，绝无硬编码。

8. V9 工具链及对照组探针测试

项目	结果
现实现 UBSan 跑全 20 点	stderr 全空 20/20 ✅
`-ftrapv` 全 20 点	`rc=0`，stderr 空
`-Wall -Wextra` 编译	0 字节警告
对照组 A 强制 `INT_MIN` 取反（UBSan）	报错 ⇒ 探针有效 ✅
对照组 B `volatile` 版 `INT_MIN` 取反（`-ftrapv`）	Abort trap: 6 ⇒ 探针有效 ✅
闸门对照组：改坏 `main.cpp` 走 `check_sample.py`	PASS=0, FAIL=20 ⇒ 闸门有效 ✅
闸门对照组：改坏 `main.py` 走 `check_new_analysis --realdata`	通过 0，失败 1 ⇒ 闸门有效 ✅

9. 数据运行逐点表

以下为部分测试数据的运行情况表（其中第 7-20 点被报告截断，故省略，但报告表明 $n$ 和 $m$ 均存在高达 $\approx 300000$ 的大样例，时间消耗保持极低，完全符合对数复杂度特性）：

点	n	m	C++ 耗时	peak RSS	树形 (maxdeg/深度)	`w==0`	`w==n`
1	992	992	13ms	37MB	9 / 42	992	0
2	99997	99997	78ms	53MB	8 / 50001	1	0
3	99996	99996	41ms	—	10094 / 50038	0	2
4	99995	99995	—	—	8 / 49998	1	0
5	99996	99996	—	—	9 / 50000	1	0
6	99994	99994	65ms	54MB	2 / 99994	—	—

整体运行情况： $n, m$ 最大测试数据规模 $\sim 300000$ ；C++ 的整体耗时在 13–78 ms，peak RSS 在 37–54 MB 左右，内存与耗时均稳定且符合预期。

目录