洞见首先 ， 第一个洞见是这道题我们使用模拟是不可行的 。 所谓的模拟也就是模拟题意的运行情况 ， 去一步一步地分析每一个玩家的选择 ， 做出最好的决策 ， 最后得出游戏的结果 。 不可行的原因也很简单 ， 因为会超时 。 这个非常明显 ， 就不深入解释了 。
除此之外 ， 我们还可以得到其他一些洞见 。 首先第一个很简单的洞见是 ， 如果Alice和Bob出生的位置相距小于da的话 ， 那么Alice必胜 。 这个也很好理解 ， 一开始的距离就在Alice的移动范围内 ， 那Bob一上来就被抓住了 。 没有讨论的余地 。 另外一个洞见是如果da >= db ， 那么Alice必胜 。
也就是如果Bob跑得比Alice慢的话 ， 他也一样必败 。 这也很简单 ， 因为地图的范围是有限的 ， 一个追一个逃 ， 逃的速度比追的慢 ， 显然他逃不出去 。 这个结论虽然简单 ， 但是反过来一想会得到一个问题 。 如果Bob跑得比Alice快的话 ， 他一定可以获胜吗？
我们看第一个案例就知道这个答案不一定 ， 因为地形也会影响最终的结果 。 树意味着每一个节点都全连通 ， 也意味着每两点的路线只有一条 。 换句话说每一条路线都是思路 ， 即使Bob跑得快如果不反向跑甩掉Alice的话 ， 那么他也是一样会被Alice追上的 。
所以我们接下来要做的就是深入分析这里的情况 ， 把剩下的问题捋清楚 。
回味样例codeforces的问题有一个特点就是我们一定要深入分析样例 ， 因为很多出题人很良心 ， 给出的样例都是关键样例 。 我们可以借助样例的情况帮助我们分析问题 。 比如今天说的这题就是一个 。
我们来分析一下第一个样例：
文章插图
这就是典型的Bob跑得比Alice快的样例 ， Bob不仅跑得比Alice快 ， 甚至还是Alice的两倍 。 但是我们都知道结果还是Alice获胜 ， 原因也很简单 ， Alice移动到1号节点之后 ， Bob只有两个选择要么1号节点要么4号节点 ， 这两个节点都距离1号节点只有一个距离 ， 仍然在Alice追上的范围内 。
在这个样例当中Bob的逃跑空间勉强是够的 ， 但还是被追上了 ， 说明他的逃跑速度是不够的 。 不够的原因也很简单 ， 因为一开始当Alice移动到1节点之后 ， 他距离Bob的距离是1 ， 也就是一个da 。 这时Bob无路可走只能折返甩开Alice ， 这时候他最多能够走一个db ， 他要想不被Alice捉住 ， 首先他需要先走过da这一段距离 ， 接着他需要走出至少da+1的距离 ， 才能保证Alice折返追他也追不到 。 那么我们可以得出一个条件是db > 2da 。
但我们发现仅仅db > 2da还是不够的 ， 因为在这个例子当中我们可以看得出来不够开阔 ， 即使db=3 ， Bob也没处可去 。 也就是说在这棵树上至少有一条链路它的长度要大于2da才行 ， 否则即使Bob再能跑也会被地形限制住 。 对于一棵树而言 ， 求它的最长链路还是比较简单的 ， 我们也在之前的文章当中讲解过 ， 其实就是对于每一个节点都求一个到叶子节点的最长距离和次长距离之和 。 所有的节点的距离最大的那个就是整棵树上的最长链路 。
我们整理一下思路 ， 一共发现了3个条件 ， 只有满足这3个条件 ， Bob才可能跑掉 ， 否则一定会被Alice捉住 。 这三个条件分别是：

1. 起始的时候Bob和Alice距离大于da
2. 树的直径大于2da
3. db大于2da

所以我们要求的就只有两点 ， 第一点是一开始它们之间的距离 ， 以及树的直径（树上最长的链路长度） 。 好在这两点都可以通过递归实现 。 都理出来了之后代码就不难写了：
t = int(input())depth = [0 for _ in range(200050)]for _ in range(t):n, a, b, da, db = list(map(int, input().split(' ')))edges = [[] for _ in range(n+2)]for i in range(n-1):u, v = list(map(int, input().split(' ')))edges[u].append(v)edges[v].append(u)diameter = 0depth[a] = 0def dfs(u, f):global diameterl = 0for v in edges[u]:if v == f:continue# depth数组记录每个节点的树深depth[v] = depth[u] + 1cur = 1 + dfs(v, u)# cur + l即u节点到叶子节点的最长距离和次长距离# 直径就是这两者和之中最大的一个diameter = max(diameter, cur + l)l = max(l, cur)return l # 以Alice所在的点作为树根 ， 这样depth[b]即Alice和Bob的距离dfs(a, -1)if depth[b]

• 上一页
• 1
• 2
• 3
• 下一页

• 手机能用多久？如果出现这3种征兆，说明“默认使用时间”已到
• 支付宝发布新规，用户如果出现这3种情况，花呗或将直接封停
• 在谷歌算法更新之后2020年盗版网站流量锐减三分之一
• 计算机专业大三学生，如果想主攻前端开发，该重视哪些内容
• 详解工程师不可不会的LRU缓存淘汰算法
• 大数据专业的同学，如果要往人工智能方向发展，该怎么选课
• 今天上海这个比赛上，获奖“程序媛”讲述了自己与算法的爱恨情仇
• 物联网专业本科生，如果未来想从事程序开发岗位，该如何准备
• 天生鸿蒙必有用：内在升华高于表象
• 花呗用户5亿人，如果“集体逾期不还”会咋样？马云自有办法