【题目来源】
洛谷：[P1600 NOIP 2016 提高组] 天天爱跑步 - 洛谷
【题目描述】
小 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\) 的观察员可以观察到多少人。
【输入样例】
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
【输出样例】
2 0 0 1 1 1
【算法标签】
《洛谷 P1600 天天爱跑步》 #线段树# #树上起发式合并# #最近公共祖先LCA# #树链剖分# #动态树LCT# #ST表# #差分# #NOIP提高组# #2016#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 300005; // 定义最大节点数int n, m; // n: 节点数, m: 路径数
int deep[N]; // 存储每个节点的深度
int f[N][25]; // 倍增数组，f[i][j]表示节点i的2^j级祖先
vector<int> ve[N]; // 邻接表存储树结构
int w[N]; // 每个节点的观察值
int u, v, s, t, l; // 临时变量// 定义路径操作结构体
struct Node
{int t; // 操作类型（0: 上行路径, 1: 下行路径）int v; // 路径参数值
};vector<Node> add[N]; // 在节点处添加的路径操作
vector<Node> del[N]; // 在节点处删除的路径操作
int cnt[2][N * 2]; // 计数器数组，[0]用于上行路径，[1]用于下行路径
int ans[N]; // 存储每个节点的答案/*** 第一次DFS：计算深度和父节点信息* @param u 当前节点* @param fa 父节点*/
void dfs_1(int u, int fa)
{deep[u] = deep[fa] + 1; // 计算当前节点深度f[u][0] = fa; // 记录直接父节点// 遍历所有子节点for (int i = 0; i < ve[u].size(); i++){int tmp_v = ve[u][i];if (tmp_v == fa) continue; // 跳过父节点dfs_1(tmp_v, u); // 递归处理子节点}
}/*** 初始化倍增数组*/
void init()
{for (int i = 1; i <= 20; i++){for (int j = 1; j <= n; j++){f[j][i] = f[f[j][i - 1]][i - 1]; // 计算2^i级祖先}}
}/*** 计算两个节点的最近公共祖先（LCA）* @param x 第一个节点* @param y 第二个节点* @return 最近公共祖先节点*/
int lca(int x, int y)
{// 确保x的深度不小于yif (deep[x] < deep[y]){swap(x, y);}// 将x提升到与y同一深度for (int i = 20; i >= 0; i--){if (deep[f[x][i]] >= deep[y]){x = f[x][i];}}// 如果x和y相同，直接返回if (x == y){return x;}// 同时提升x和y直到它们的父节点相同for (int i = 20; i >= 0; i--){if (f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0]; // 返回最近公共祖先
}/*** 第二次DFS：统计路径信息并计算答案* @param x 当前节点*/
void dfs_2(int x)
{// 记录当前计数器的值（用于差分计算）int pre_1 = cnt[0][w[x] + deep[x] + N];int pre_2 = cnt[1][w[x] - deep[x] + N];// 处理当前节点的添加操作for (int i = 0; i < add[x].size(); i++){Node sn = add[x][i];cnt[sn.t][sn.v + N]++; // 增加对应计数}// 处理当前节点的删除操作for (int i = 0; i < del[x].size(); i++){Node sn = del[x][i];cnt[sn.t][sn.v + N]--; // 减少对应计数}// 递归处理所有子节点for (int i = 0; i < ve[x].size(); i++){int tmp_v = ve[x][i];if (tmp_v == f[x][0]) continue; // 跳过父节点dfs_2(tmp_v); // 递归处理子节点}// 计算当前节点的答案（差分计算）ans[x] = cnt[0][w[x] + deep[x] + N] + cnt[1][w[x] - deep[x] + N] - pre_1 - pre_2;return;
}int main()
{// 输入节点数和路径数cin >> n >> m;// 输入树的边for (int i = 1; i < n; i++){cin >> u >> v;ve[u].push_back(v);ve[v].push_back(u);}// 输入每个节点的观察值for (int i = 1; i <= n; i++){cin >> w[i];}// 第一次DFS：预处理深度和父节点信息dfs_1(1, 0);init(); // 初始化倍增数组// 处理每条路径for (int i = 1; i <= m; i++){cin >> s >> t;l = lca(s, t); // 计算最近公共祖先// 处理上行路径（s到lca）add[s].push_back({0, deep[s]});del[f[l][0]].push_back({0, deep[s]});// 处理下行路径（lca到t）add[t].push_back({1, deep[s] - 2 * deep[l]});del[l].push_back({1, deep[s] - 2 * deep[l]});}// 第二次DFS：计算每个节点的答案dfs_2(1);// 输出所有节点的答案for (int i = 1; i <= n; i++){cout << ans[i] << " ";}cout << endl;return 0;
}
【运行结果】
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
2 0 0 1 1 1