[NOIP 2016 提高组] 天天爱跑步

GitHub 跳转原题关系图返回列表

把路径观察条件改写为深度键值，在树形 DFS 中用事件计数统计经过人数。

OJ: luogu

题目 ID: P1600

难度:提高

标签:LCA树形差分事件计数python

日期: 2026-07-17 02:00

题意

每个玩家沿最短路径跑步，每个节点在指定时刻观察，统计每个观察员能看到的玩家数。

思路

路径拆成 s -> lca 和 lca -> t 两段。第一段满足 depth[s] = depth[u] + w[u]；第二段满足 depth[s]-2*depth[lca] = w[u]-depth[u]。把两类键作为事件挂到端点，在显式后序 DFS 中用桶计数，进入子树前后的差就是该节点贡献。

Python 知识

defaultdict(list) 按节点收集稀疏事件，避免创建大量空事件容器。
array("i") 保存祖先、计数和答案；显式栈模拟后序 DFS。
事件元组 (key, delta) 直接表达加一和减一。

代码

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
91import sys
from array import array
from collections import defaultdict


input = sys.stdin.buffer.readline
n, players = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
watch = [0] + list(map(int, input().split()))

parent = array("i", [0]) * (n + 1)
depth = array("i", [0]) * (n + 1)
order = array("i", [1])
for node in order:
    for neighbor in graph[node]:
        if neighbor != parent[node]:
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            order.append(neighbor)

ancestors = [parent]
for _ in range(1, n.bit_length()):
    previous = ancestors[-1]
    ancestors.append(array("i", (previous[previous[node]] for node in range(n + 1))))


def lca(x, y):
    if depth[x] < depth[y]:
        x, y = y, x
    difference = depth[x] - depth[y]
    bit = 0
    while difference:
        if difference & 1:
            x = ancestors[bit][x]
        difference >>= 1
        bit += 1
    if x == y:
        return x
    for level in range(len(ancestors) - 1, -1, -1):
        if ancestors[level][x] != ancestors[level][y]:
            x = ancestors[level][x]
            y = ancestors[level][y]
    return parent[x]


events_up = defaultdict(list)
events_down = defaultdict(list)
offset = n + 2
for _ in range(players):
    start, end = map(int, input().split())
    ancestor = lca(start, end)
    events_up[start].append((depth[start], 1))
    if ancestor != 1:
        events_up[parent[ancestor]].append((depth[start], -1))
    key = depth[start] - 2 * depth[ancestor] + offset
    events_down[end].append((key, 1))
    events_down[ancestor].append((key, -1))

bucket_size = 2 * n + 5
count_up = array("i", [0]) * bucket_size
count_down = array("i", [0]) * bucket_size
answer = array("i", [0]) * (n + 1)
stack = []
key_up = depth[1] + watch[1]
key_down = watch[1] - depth[1] + offset
stack.append([1, 0, count_up[key_up], count_down[key_down]])
while stack:
    node, child_index, before_up, before_down = stack[-1]
    if child_index < len(graph[node]):
        neighbor = graph[node][child_index]
        stack[-1][1] += 1
        if neighbor == parent[node]:
            continue
        key_up = depth[neighbor] + watch[neighbor]
        key_down = watch[neighbor] - depth[neighbor] + offset
        stack.append([neighbor, 0, count_up[key_up], count_down[key_down]])
        continue
    for key, delta in events_up.get(node, ()):
        count_up[key] += delta
    for key, delta in events_down.get(node, ()):
        count_down[key] += delta
    key_up = depth[node] + watch[node]
    key_down = watch[node] - depth[node] + offset
    answer[node] = count_up[key_up] - before_up + count_down[key_down] - before_down
    stack.pop()

print(" ".join(map(str, answer[1:])))

原有 C++ 版本仍保留：

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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300000 + 5;
const int LOG = 20;

struct Frame {
    int u;
    int before1;
    int before2;
};

int n, m;
vector<int> g[MAXN];
int w[MAXN];

int parent_arr[MAXN];
int depth_arr[MAXN];
int up[MAXN][LOG];
int iter_idx[MAXN];

// 第一类事件：处理 s -> lca 这一段，key = depth[s]
vector<pair<int, int>> event1[MAXN];
// 第二类事件：处理 lca -> t 这一段（不含 lca），key = depth[s] - 2 * depth[lca] + offset
vector<pair<int, int>> event2[MAXN];

// 当前“已完成后序统计的子树”里，两类 key 的出现次数。
vector<int> cnt1;
vector<int> cnt2;
// 第二类 key 可能为负，整体平移后再开桶统计。
int offset_value;
int bucket_limit;

int answer[MAXN];

void init_tree(int n) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        event1[i].clear();
        event2[i].clear();
        parent_arr[i] = 0;
        depth_arr[i] = 0;
        iter_idx[i] = 0;
        answer[i] = 0;
        for (int j = 0; j < LOG; j++) {
            up[i][j] = 0;
        }
    }
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 非递归建树，顺便预处理父亲和倍增祖先表。
// 题目提示可能栈溢出，所以这里不用递归 DFS。
void build_lca() {
    vector<int> st;
    st.push_back(1);
    parent_arr[1] = 0;
    depth_arr[1] = 0;
    for (int j = 0; j < LOG; j++) {
        up[1][j] = 1;
    }

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_arr[u]) {
                continue;
            }

            parent_arr[v] = u;
            depth_arr[v] = depth_arr[u] + 1;
            up[v][0] = u;
            for (int j = 1; j < LOG; j++) {
                up[v][j] = up[up[v][j - 1]][j - 1];
            }

            st.push_back(v);
        }
    }
}

int kth_ancestor(int u, int k) {
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            u = up[u][j];
        }
    }
    return u;
}

int lca(int a, int b) {
    if (depth_arr[a] < depth_arr[b]) {
        swap(a, b);
    }

    a = kth_ancestor(a, depth_arr[a] - depth_arr[b]);
    if (a == b) {
        return a;
    }

    for (int j = LOG - 1; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }

    return up[a][0];
}

void add_event(vector<pair<int, int>> events[], int node, int key, int delta) {
    if (0 <= key && key <= bucket_limit) {
        events[node].push_back(make_pair(key, delta));
    }
}

void solve() {
    // 第一类 key 最大不超过 n，第二类 key 平移后也能落在 [0, 2n] 里。
    bucket_limit = 2 * n + 5;
    offset_value = n + 2;
    cnt1.assign(bucket_limit + 1, 0);
    cnt2.assign(bucket_limit + 1, 0);

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

        int p = lca(s, t);

        // 把一条路径 s -> t 拆成两段：
        // 1. s -> lca(s, t)
        // 2. lca(s, t) -> t（不含 lca）
        //
        // 对于第一段，u 被看到的条件是：
        // depth[s] - depth[u] == w[u]
        // 也就是 depth[s] == depth[u] + w[u]
        add_event(event1, s, depth_arr[s], 1);
        if (p != 1) {
            // 在 parent(lca) 处挂 -1，表示上升段到 lca 为止。
            add_event(event1, parent_arr[p], depth_arr[s], -1);
        }

        // 对于第二段，u 被看到的条件是：
        // depth[s] - 2 * depth[lca] + depth[u] == w[u]
        // 也就是 depth[s] - 2 * depth[lca] == w[u] - depth[u]
        //
        // 这里把左边这一项作为第二类 key。
        int key = depth_arr[s] - 2 * depth_arr[p] + offset_value;
        add_event(event2, t, key, 1);
        // 第二段不包含 lca，所以在 lca 本身挂 -1。
        add_event(event2, p, key, -1);
    }

    vector<Frame> st;
    int key1_root = depth_arr[1] + w[1];
    int key2_root = w[1] - depth_arr[1] + offset_value;
    st.push_back({1, (0 <= key1_root && key1_root <= bucket_limit) ? cnt1[key1_root] : 0,
                  (0 <= key2_root && key2_root <= bucket_limit) ? cnt2[key2_root] : 0});

    // 显式栈模拟后序 DFS。
    // before1 / before2 记录“进入 u 子树前”桶中目标 key 的值。
    // 退出 u 时再读取一次，二者差值就是整棵子树给 u 带来的贡献。
    while (!st.empty()) {
        int u = st.back().u;

        if (iter_idx[u] < (int)g[u].size()) {
            int v = g[u][iter_idx[u]++];
            if (v == parent_arr[u]) {
                continue;
            }

            int key1 = depth_arr[v] + w[v];
            int key2 = w[v] - depth_arr[v] + offset_value;
            int before1 = (0 <= key1 && key1 <= bucket_limit) ? cnt1[key1] : 0;
            int before2 = (0 <= key2 && key2 <= bucket_limit) ? cnt2[key2] : 0;
            st.push_back({v, before1, before2});
        }
        else {
            // 所有孩子都处理完后，再把挂在 u 上的事件加入桶。
            for (size_t i = 0; i < event1[u].size(); i++) {
                cnt1[event1[u][i].first] += event1[u][i].second;
            }
            for (size_t i = 0; i < event2[u].size(); i++) {
                cnt2[event2[u][i].first] += event2[u][i].second;
            }

            int key1 = depth_arr[u] + w[u];
            int key2 = w[u] - depth_arr[u] + offset_value;
            int cur1 = (0 <= key1 && key1 <= bucket_limit) ? cnt1[key1] : 0;
            int cur2 = (0 <= key2 && key2 <= bucket_limit) ? cnt2[key2] : 0;

            // 两次读数的差值，正好是“u 子树中能对 u 产生贡献的路径数量”。
            answer[u] = (cur1 - st.back().before1) + (cur2 - st.back().before2);
            st.pop_back();
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';
}

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

    cin >> n >> m;
    init_tree(n);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    build_lca();

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

    solve();

    return 0;
}

复杂度

预处理 O(n log n)，路径事件和 DFS 总计 O((n+m)log n)。

总结

跑步时刻条件本质是深度等式；把等式变成键值后，树形子树计数就能批量完成。

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

题目背景

NOIP2016 提高组 D1T2

题目描述

小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

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

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

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

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 $j$ 作为终点的玩家：若他在第 $w_j$ 秒前到达终点，则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $w_j$ 秒到达终点，则在结点 $j$ 的观察员可以观察到这个玩家。

输入格式

第一行有两个整数 $n$ 和 $m$ 。其中 $n$ 代表树的结点数量，同时也是观察员的数量， $m$ 代表玩家的数量。

接下来 $n-1$ 行每行两个整数 $u$ 和 $v$ ，表示结点 $u$ 到结点 $v$ 有一条边。

接下来一行 $n$ 个整数，其中第 $j$ 个整数为 $w_j$ ，表示结点 $j$ 出现观察员的时间。

接下来 $m$ 行，每行两个整数 $s_i$ ，和 $t_i$ ，表示一个玩家的起点和终点。

对于所有的数据，保证 $1\leq s_i,t_i\leq n, 0\leq w_j\leq n$ 。

输出格式

输出 $1$ 行 $n$ 个整数，第 $j$ 个整数表示结点 $j$ 的观察员可以观察到多少人。

输入输出样例 #1

输入 #1

text

1
2
3
4
5
6
7
8
9
106 3
2 3
1 2 
1 4 
4 5 
4 6 
0 2 5 1 2 3 
1 5 
1 3 
2 6

输出 #1

text

12 0 0 1 1 1

输入输出样例 #2

输入 #2

text

输出 #2

text

11 2 1 0 1

说明/提示

样例 1 说明

对于 $1$ 号点， $w_i=0$ ，故只有起点为 $1$ 号点的玩家才会被观察到，所以玩家 $1$ 和玩家 $2$ 被观察到，共有 $2$ 人被观察到。

对于 $2$ 号点，没有玩家在第 $2$ 秒时在此结点，共 $0$ 人被观察到。

对于 $3$ 号点，没有玩家在第 $5$ 秒时在此结点，共 $0$ 人被观察到。

对于 $4$ 号点，玩家 $1$ 被观察到，共 $1$ 人被观察到。

对于 $5$ 号点，玩家 $1$ 被观察到，共 $1$ 人被观察到。

对于 $6$ 号点，玩家 $3$ 被观察到，共 $1$ 人被观察到。

子任务

每个测试点的数据规模及特点如下表所示。

提示：数据范围的个位上的数字可以帮助判断是哪一种数据类型。

测试点编号	$n=$	$m=$	约定
$1\sim 2$	$991$	$991$	所有人的起点等于自己的终点，即 $\forall i,\ s_i=t_i$
$3\sim 4$	$992$	$992$	所有 $w_j=0$
$5$	$993$	$993$	无
$6\sim 8$	$99994$	$99994$	$\forall i\in[1,n-1]$ ， $i$ 与 $i+1$ 有边。即树退化成 $1,2,\dots,n$ 按顺序连接的链
$9\sim 12$	$99995$	$99995$	所有 $s_i=1$
$13\sim 16$	$99996$	$99996$	所有 $t_i=1$
$17\sim 19$	$99997$	$99997$	无
$20$	$299998$	$299998$	无

提示

（提示：由于原提示年代久远，不一定能完全反映现在的情况，现在已经对该提示做出了一定的修改，提示的原文可以在该剪贴板查看）

在最终评测时，调用栈占用的空间大小不会有单独的限制，但在我们的工作环境中默认会有 $1 \text{MiB}$ 的限制。这可能会引起函数调用层数较多时，程序发生栈溢出崩溃，程序中较深层数的递归往往会导致这个问题。如果你的程序需要用到较大的栈空间，请务必注意该问题。

我们可以使用一些方法修改调用栈的大小限制。

Linux

我们可以在终端中输入下列命令：ulimit -s 1048576。此命令的意义是，将调用栈的大小限制修改为 $1048576\text{KiB}=1 \text{GiB}$ 。

例如，对于如下程序 sample.cpp：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include <bits/stdc++.h>
using namespace std;
int f[1000005];
void dfs(int a){
	if(a == 0){
		f[a] = 0;
		return;
	}
	dfs(a - 1);
	f[a] = f[a - 1] + 1;
}
int main(){
	dfs(1000000);
	return 0;
}

将上述源代码用命令 g++ sample.cpp -o sample 编译为可执行文件 sample 后，使用 ./sample 执行程序。

如果在没有使用命令 ulimit -s 1048576 的情况下运行该程序，sample 会因为栈溢出而崩溃；如果使用了上述命令后运行该程序，该程序则不会崩溃。

特别地，当你打开多个终端时，它们并不会共享该命令，你需要分别对它们运行该命令。

请注意，调用栈占用的空间会计入总空间占用中，和程序其他部分占用的内存共同受到内存限制。

Windows

如果你使用 Windows 下的 Dev-C++，请选择 工具-编译选项 并在如下区域填入以下命令 -Wl,--stack=1073741824，填入后注意确认“编译时加入以下命令的”的框是已勾选状态。

此处 1073741824 的单位是 $\text{B/Bytes}$ 。

[NOIP 2016 提高组] 天天爱跑步

目录

题意

思路

Python 知识

代码

复杂度

总结