首页 > 试题广场 >

寻找牛妹

[编程题]寻找牛妹

有n个房间，房间之间有通道相连，一共有n-1个通道，每两个房间之间都可以通过通道互相到达。

牛牛一开始在1号房间。牛妹在某个另外的房间。牛牛想去寻找牛妹，但是他没有地图，所以只能在房间之间乱走。

牛牛每走过一条通道需要花费1金币，每条通道最多只能走两次。

牛牛有一个乱走规则：如果当前牛牛有 没走过的通道 可以走，牛牛就不会去走 走过一次的通道

这个规则可以保证只要钱足够就一定可以找到牛妹。

有m个查询，每次询问如果牛妹在 $x_i$ 号房间，请问牛牛身上至少要带多少金币才可以保证任何情况下都可以找到牛妹。

示例1

输入

4,1,[1,2,2],[2,3,4],[3]

[4]

花费金币最多的方案是1->2->4->2->3



第一个参数n代表房间数量
第二个参数m代表查询数量
第三、四个参数vector u,v代表通道，与通过通道相连
第五个参数vector x代表m次查询中牛妹的位置

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

树

难度：

0条回答 9收藏 3230浏览

查看代码

扫一扫，把题目装进口袋