Book of Evil 题目大意 就是给定一棵 个点的树🌲，有 个关键点问你有多少个点满足到关键点的最大距离小于等于 分析 到关键点的最大距离无非就是，所以就可以分别跑两次 ，求子树内外的信息即可然后所有的都可以直接初始化为无穷小，表示子树内/外不存在关键点遇到关键点把距离设为 即可 C
展开全文
分析 我们有一个性质，树的任意一个点到树另外一个点的最长距离，一定是由某一个直径的端点和该点构成的。有了这个性质。我们只需要对这几个特殊的建一个虚树。然后找到直径的端点，那么答案为 这个做三次 就好了。代码非常简单，因为我们不用真正的建出虚树。 关于定理的证明，下文全选自 网站。 引理：在
展开全文
分析 我们发现一个点是否可以作为魔法书的点当且仅当距离他最近的点的距离所以我们可以像求树的直径一样DP求得每个点向下的距离最大值和距离次大值以及向上的距离最大值最后在求完之后，统计一下有多少个点满足 即可时间复杂度：期望得分：100分 代码 //CF337D
#include <algorit
展开全文
思路 1.把鬼的位置存起来，双向边建树 2.进行一遍dfs找到离树根最远的鬼 3.对该点进行一遍dfs找到离该鬼点最远的鬼点 4.再对鬼点进行一遍dfs，即找出两个相邻最远的鬼点 5.此时如果有点满足到这两个鬼点小于等于d，则成立 代码 #include <bits/stdc++.h>
展开全文
一点细节没写好结果疯了..... 按照求树直径那样出子树内的最远距离 然后换根求子树外的最远距离 所以数组设置为无穷小,因为我们要求的是最大 #include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int
展开全文
Book of Evil 分析 如果想要作为一个放置点，那么一个点距离一个魔鬼的最大值不能超过 d 。考虑到最大距离的产生方式——子树内部以及外部。那么可以分两步做 求出一个节点距离子树内部的鬼的最远距离从叶子结点更新到根节点 开始更新子树外的最远距离，dfs一遍，从上往下更新。 更新方式：记
展开全文
题目： 给你一棵个结点的树。给个标记结点，距离。问树上有几个结点到所有标记结点的距离均。 做法： 考虑做一个树，表示结点到所有标记结点的最大距离。求出之后，一遍看有多少就出结果了。这个树怎么做呢？先一遍求出以结点为根的子树下的标记到的最大距离，放到（若子树下无标记则为）。然后第二遍换根转移，每次
展开全文
题目描述 第一行输入 n m d 三个整数，数量级是 1e5。n 代表有n个节点的树，m 代表存在 m 个特殊的节点，这些节点被感染了。在下面 n - 1 行给出对应的树边关系。现在询问的是，在这棵树中存在几个节点到全部被感染的节点距离都要小于等于 d 。 Solution 对于输入的被感染节点，我
展开全文
题目大意：给你一棵树，树上有个特殊点，问有多少点到所有特殊点的距离小于d.思路：又是学习大佬题解的一天我好菜啊先对特殊点求一个树的直径，然后枚举所有点，如果它到直径两端的距离小于等于d，说明这些点满足题目要求。求特殊点的直径，三次DFS即可，先从根求一波最长的特殊点，然后从特殊的再求一波最长的另外一
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
