《天天爱跑步》是一个养成类游戏,主要玩法如下:
游戏地图
游戏的地图可以看作一棵包含 \( n \) 个结点和 \( n-1 \) 条边的树。
每个结点编号为从 1 到 \( n \) 的连续正整数。
玩家起点和终点
有 \( m \) 个玩家,每个玩家有一个起点 \( s_i \) 和一个终点 \( t_i \)。
游戏过程
每天打卡任务开始时,所有玩家在第 0 秒同时从自己的起点出发。
玩家以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去。
玩家跑到终点后,该玩家就算完成了打卡任务。
观察员
在每个结点上都放置了一个观察员。
如果玩家在第 \( w_j \) 秒到达终点,则在结点 \( j \) 的观察员可以观察到这个玩家。
活跃度计算
观察员可以观察到在某个结点到达的玩家数量,这可以用来衡量游戏的活跃度。
具体算法
路径拆分
将一条路径拆分为往上和往下两条路径。
设路径的起点为 \( u \),终点为 \( v \),他们的最低公共祖先(LCA)为 \( p \)。
上行的路可以对 \( x \) 造成贡献当且仅当 \( dep[u] - dep[x] = w_x \),移项得 \( dep[u] = w_x + dep[x] \)。
观察者贡献
对于把结点 \( j \) 作为终点的玩家,如果在第 \( w_j \) 秒前到达终点,则在结点 \( j \) 的观察员不能观察到该玩家;
如果正好在第 \( w_j \) 秒到达终点,则在结点 \( j \) 的观察员可以观察到这个玩家。
示例输入输出
输入:
```
n = 4
m = 2
edges = [(1, 2), (1, 3), (2, 4)]
watch_times = [0, 2, 4]
player_starts = [1, 2]
player_ends = [3, 4]
```
输出:
```
[2, 0, 1, 1]
```
解释:
在结点 1,有 2 个玩家(1 和 2)在 0 秒到达,所以观察到 2 人。
在结点 2,没有玩家在 2 秒到达,所以观察到 0 人。
在结点 3,有 1 个玩家(2)在 4 秒到达,所以观察到 1 人。
在结点 4,有 1 个玩家(1)在 4 秒到达,所以观察到 1 人。
建议
玩家需要每天按时上线完成打卡任务,以保持游戏的连续性和活跃度。
观察员机制可以帮助了解每个结点的活跃情况,从而优化游戏设计。