Description Solution 可以把题目转化成求 1-n 里到点集S的最远距离最小的结果，而这个点应该出现在点集S中离得最远的两个点连线的中点上。而点集S的最远距离就是求直径，直接dfs的复杂度是 的，但是我们可以通过处理出LCA，先找到深度最大的点作为直径的一端，另一端通过枚举得
展开全文
题目链接 题意：题解：AC代码 /*
Author : zzugzx
Lang : C++
Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#def
展开全文
MMSet2 思路 这道题目显然能够通过的复杂度来暴力，这显然不能达到题目要求的复杂度，因此我们可以对题目要求我们计算的东西进行转换。 某个点到所有点集的最大距离最小，这就有点像是重心的求法了，但是这题又有所不同，如果这是在一颗树上，显然我们可以很快的得到答案，，所以这题我们也可以转换思想，每次求解
展开全文
问题转化为找s集合中距离最远的两点的距离 #include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int n,m,he[maxn];
int read(){
int x; scanf("%d"
展开全文
将求树的直径的过程进行模拟即可~ #include <bits/stdc++.h>
using namespace std;
const int N=3e5+50,M=20;
vector<int>v[N];
int dep[N],w[N],f[N][M];
void dfs
展开全文
MMSet2 题目地址： https://ac.nowcoder.com/acm/problem/14250 基本思路： 题目重点是我们要弄清楚题目中每次询问的到底是什么, 我们要求的是 这个式子实际上是让我们找到任意一个点,这个点到集合内每个点的距离的最大值最小,到集合内任意点的距离的最
展开全文
题意简述： 有一个 个节点的树，点编号为 。有 次询问。每次询问给出一个子集 ，令 。其中 表示点 与点 的距离。求 。 做法简述 因为 ，所以 。暴力求的话，复杂度是平方的。我们需要优化。从等式的右边的意思出发。我们需要求的就是某个点 ，它到点集中所有点的最大距离最小。因为要求最小，所
展开全文
1.离线算法(只能求一组固定的数据，如果新的数据来了就要重新求一次):Tarjan(离线):https://www.cnblogs.com/JVxie/p/4854719.html模板:https://www.it610.com/article/4607682.htm要用到并查集的知识:https:
展开全文
解题思路 读懂题目，这个题目就做对了一半了。第一行给出一个数n，n<3e5，代表这棵树的节点数，下面n-1行给出节点连边关系。后面给出一个q，代表q组询问，每次询问，都是一行。第一行代表询问的集合点数目，接着给出这些点。需要我们求解的是，在整棵树中，找出某一个点，距离集合中点的最大距离最小。之
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
