题意 给你一棵有 个节点的树，要求在所有叶子节点到根节点的路径上有一个节点是特殊的（军队）。问如果要封死这棵树，移动距离最大的点移动的最小距离是多少？ 分析 这题挺恼火的，一步一步慢慢来 首先：树上倍增先预处理用存储 节点的第 个祖先的节点编号， 存储 节点到它的第 个祖先的路径长度。在
展开全文
Description H 国有n 个城市，这 n 个城市用n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。 H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都
展开全文
题意：给你一个有n个城市的国家，n-1道路将城市连接（即为树），首都为节点1，有m支军队，每支军队可以在一个城市设立一个检查点，问使从首都到任意一个边境节点都会碰到检查点军队移动最少时间为多少，军队可以同时移动。 思路：如果军队数少于与首都直接相连的节点数则输出-1，否则一定有解。我们可以发现时间越
展开全文
做法：倍增+二分+贪心 思路： 1.类似于lca的方法，倍增预处理出fa父亲节点和depth到父亲节点的长度数组。 2.二分答案。 3.对于每个当前的mid，把每个军队上提到能够达到的最高位置（最高上提到根节点的子节点）。 4.对于可以上提到根节点的子节点，再经过根节点后还能行走的军队，存入res
展开全文
思路 显而易见,答案具有单调性,时间越长,越容易控制疫情.所以很容易想到二分时间.首先,占据一个点肯定不如占据这个点的父亲,因此时间内到达不了号节点的尽力往上跳就可以了(暴力跳可不行,需要使用倍增).还有一些军队可能会经过号节点到达其他号节点的儿子节点.先来证明一个结论:若些军队的集合不经过号节点能
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
