人人好,迎接阅读周末算法题专题。

今天选择的算法题来源于昨天统一套题中的D题,这题全场通过的人数在2600人左右。虽然通过的人数更少了一些,然则问题的难度却并没有增添许多,然则意见意义度增添了。我也是第一次遇见这样的问题。

问题链接:https://codeforces.com/contest/1405/problem/D

空话不多说,我们一起来看这题的题意。

题意


我们都知道数据结构当中的树有这样一个性子,若是树当中有n个点,那么它应该由n-1条无向边组成。而且树当中是一定没有环的,若是有环的话n-1条边就不够了。

今天是说有两个人划分叫做Alice和Bob在一棵树上玩游戏,这两个人名是业内的老例。通常两个人玩游戏的问题,主人公的名字许多都叫Alice和Bob,我也不知道这个老例的由来,人人知道这么回事就好了。Alice和Bob两人各自占有了树上的一个点,然后两个人交替移动。Alice先手,Bob后手。

Alice每一次移动最多可以移动da距离,Bob最多可以移动db距离,两个人也可以放弃移动。假设两人都绝顶聪明每一次都市选择最佳计谋,叨教经由最多个回合之后,Alice能否捉到Bob呢?若是可以则Alice获胜,否则Bob获胜。注意在Bob的回合,它可以经由Alice的节点,这并不会被视为捉到。

不知道为什么看到这道题的时刻,总是会想起费玉清的段子,不知道你们有没有这种感受。

样例


第一行输入一个数t,示意测试数据的组数。

对于每组数据首先有5个数,划分是n, a, b, da, db。n示意树节点的个数,a和b示意游戏开始时a和b出生点的位置。da和db示意Alice和Bob每回合最多移动的距离。这几个数的最大局限都是,而且多组数据当中所有的n相加不跨越

我们来看两组样例:

4 3 2 1 2
1 2
1 3
1 4
6 6 1 2 5
1 2
6 5
2 3
3 4
4 5

第一组数据是这样的:

蓝色示意Alice,红色是Bob。由于Alice先手,只要Alice移动到1节点,无论Bob若何移动,他都必输无疑。

第二组数据:

由于Alice最多只能移动两格,第一回合移动到3,Bob选择不动。只要Alice移动,不论是一格照样两格,Bob都可以直接移动到1节点。也就是说最终Bob就在1和6节点之间往返移动,躲开Alice的追捕。

题解


看到Alice和Bob两人游戏,而且两人都绝顶聪明会选择最佳计谋,首先想到的就是博弈论。然则考察一下你会发现这题和博弈论没有什么关系,由于博弈论往往都是公正博弈,局势会有状态转移。但这题当中不是,这题不存在输赢状态转移,一定会有一个确定的效果,就是是谁胜谁负,以是这题不知足博弈论的条件。

,

以太坊统计网

www.326681.com采用以太坊区块链高度哈希值作为统计数据,联博以太坊统计数据开源、公平、无任何作弊可能性。联博统计免费提供API接口,支持多语言接入。

,

类似博弈论的题面只是障眼法而已,若是你信了,而且真的往这方面起劲,那么你就被出题人骗了。不外这个陷阱照样对照显著的,很容易看出来。接下来我们又遇到了另外一个陷阱,这个陷阱也很显著,就是执行的回合数目。问题给的是,这个数是真正的天文数字,比宇宙当中所有的粒子数都要多。以是我们可以完全可以明了成无限游戏。

若是出题人阴险一点,完全可以给一个这个量级的回合数,会更有欺骗性一些。实在我们想一下就会发现,树上节点最多只有个,当它们玩追逐游戏的时刻,只会有两种情形,一种是永远也追不上,另有一种是很快就追上。以是这个回合数没什么意义,就是唬人的。

洞见


首先,第一个洞见是这道题我们使用模拟是不可行的。所谓的模拟也就是模拟题意的运行情形,去一步一步地剖析每一个玩家的选择,做出最好的决议,最后得出游戏的效果。不可行的缘故原由也很简朴,由于会超时。这个异常显著,就不深入注释了。

除此之外,我们还可以获得其他一些洞见。首先第一个很简朴的洞见是,若是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 = 0

    depth[a] = 0
    def dfs(u, f):
        global diameter
        l = 0
        for v in edges[u]:
            if v == f:
                continue
            # depth数组纪录每个节点的树深
            depth[v] = depth[u] + 1
            cur = 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] <= da or da * 2 >= diameter or da*2 >= db:
        print('Alice')
    else:
        print('Bob')

我们把整个思绪说穿了是不是有一种一文不值的感受?然则自己思索要想明了照样不太容易的,codeforces的问题就是这样,经常需要我们在纸上画一画看一看。有时刻一些点靠自己想很难完全想明了,然则找一个例子试一试一下就清晰了。这也是codeforces问题有趣的地方之一。