https://www.luogu.org/problem/show?pid=1600
小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。«天天爱跑步»是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。
这个游戏的地图可以看作一一棵包含
个结点和
条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从
到
的连续正整数。
现在有
个玩家,第
个玩家的起点为
,终点为
。每天打卡任务开始时,所有玩家在第
秒同时从自己的起点出发, 以每秒跑一条边的速度, 不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是唯一的)
小C想知道游戏的活跃度, 所以在每个结点上都放置了一个观察员。 在结点
的观察员会选择在第
秒观察玩家, 一个玩家能被这个观察员观察到当且仅当该玩家在第
秒也理到达了结点
。 小C想知道每个观察员会观察到多少人?
注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏, 他不能等待一 段时间后再被观察员观察到。 即对于把结点
作为终点的玩家: 若他在第
秒重到达终点,则在结点
的观察员不能观察到该玩家;若他正好在第
秒到达终点,则在结点
的观察员可以观察到这个玩家。
输入格式：
第一行有两个整数
和
。其中
代表树的结点数量, 同时也是观察员的数量,
代表玩家的数量。
接下来
行每行两个整数
和
,表示结点
到结点
有一条边。
接下来一行
个整数,其中第
个整数为
, 表示结点
出现观察员的时间。
行,每行两个整数
,和
,表示一个玩家的起点和终点。
对于所有的数据,保证
。
输出格式：
输出1行
个整数,第
个整数表示结点
的观察员可以观察到多少人。
输入样例#1：
输出样例#1：
输入样例#2：
输出样例#2：
测试点1——5：
数组a[i][j]表示点i在j时刻经过的人数，然后一个人一个人的dfs，记录时刻time
如果到了终点，递归回退时a[now][time]++
令watch[i]=j表示i号节点观察员在j时刻出现
输出a[i][watch[i]]
测试点6——8：
树退化为一条链，而且点的编号就是深度
所以对于链上一个观察员，他只能观察到从两个位置出发的人i+watch[i]，i-watch[i]
如果i能观察到起点深度比他小的人，那么这个人的终点要>=i
如果i能观察到起点深度比他大的人，那么这个人的终点要<=i
所以，
用链表存储从每个节点起跑的人，
枚举每个观察员，然后判断两个位置的人是否满足要求
测试点9——12：
所有人的起点都是1，假设1号的深度为0，
那么只有观察员节点的深度等于出现时间，他才能观察到
所以先判断深度是否等于出现时间，不等，直接输出0，下一个
若相等，他一定能观察到经过他的所有人
也就是说，以观察员i为根的子树中有跑步者的终点，观察员i就能观察多少人
所以，终点+1，记录每个节点的深度，我用的bfs，单后dfs统计子树1的个数，
kids[]表示答案
测试点13——16：
所有人的终点都是1
也就是说，第i个观察员只能观察到第deep[i]+watch[i]层的跑步者
所以，若跑步者能被观察员i观察到，要满足以下两个条件：
1、在起点观察员i的子树内
2、起点的层数=deep[i]+watch[i]
先对原树dfs一遍，记录观察员i的子树dfs序范围in[i]——out[i]
对每一层维护一颗线段树，动态开节点
查询时，找到deep[i]+watch[i]这一层的线段树，查in[i]——out[i]有多少个起点
所有暴力综合代码
作者：xxy
本文版权归作者所有，转载请用链接，请勿原文转载，Thanks♪(･ω･)ﾉ。