[ABC148F] Playing Tag on Tree()

2023-03-04

题目

题目传送门

翻译

翻译

难度&重要性(1~10):5

题目来源

AtCoder

题目算法

最短路

解题思路

考虑到 T 想活得久， A 想尽早追上 T ,所以我们就将问题转化为在树上找一条最长链，使得 T 能比 A 先到达这条链。
所以我们就可以在树上跑两遍单源最短路，因为边权为 \(1\)，所以用 BFS 就可以了

完成状态

已完成

————————

2023-03-04

题目

题目传送门

翻译

翻译

难度&重要性(1~10):5

题目来源

AtCoder

题目算法

最短路

解题思路

考虑到 T 想活得久， A 想尽早追上 T ,所以我们就将问题转化为在树上找一条最长链，使得 T 能比 A 先到达这条链。
所以我们就可以在树上跑两遍单源最短路，因为边权为 \(1\)，所以用 BFS 就可以了

完成状态

已完成