首先题目给出是一棵树 我们可以知道树上两点路径唯一 其次又有一条额外免费的边 所以我们可以这么考虑，x,y之间的路径要么是 在原树上由x到y，要么经过额外免费的边 对于每个询问，取三种情况最小值即可 ll n,m,p;
struct node{
int e,next;
}edge[maxn]
展开全文
小A的最短路 思路 树上问题求两个点的最短距离，显然能用来进行的查询，引入了两个无边权的点，所以我们的路劲就可以规划成三种，只要在这三个当中取一个最小值就行了。接下来就是考虑求了，有一种较为快速的求的在线方法，那就是树链剖分，于是套上去(个人认为树剖求较为好写)，然后就可以开始最短路求解了。 代码
展开全文
题目 小A这次来到一个景区去旅游，景区里面有 N 个景点，景点之间有 N-1 条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去
展开全文
思路： 如果没有缆车的话，就是一个利用LCA求树上任意两点距离的板子题。（有了缆车，其实还是板子题……） 有了一个缆车之后，无非就算考虑一下要不要坐缆车以及怎样坐缆车，所以：不坐缆车xy的距离就是原来的距离dist(x,y)，坐缆车的话要考虑是x到u点坐缆车，还是到v点坐缆车，即dist(x,
展开全文
题意：有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？ 思路：求任意两点树上的距离应该用LCA.由于多了个电缆，所以我们从x到y是有3种方案：①从x直接到y，不坐电缆。②从x到u，再从u坐电缆
展开全文
题面大意 Solution #pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <
展开全文
先不看线缆，会发现，直接用lca求最短路就行了加上线缆，就多加一个判断即可比如询问x到y，线缆是j到k在dis(x,y)，dis(x,j)+dis(k,y)，dis(x,k)+dis(j,y)这三个中取最小 #include <cstdio>
#include <iostream&
展开全文
题目描述：小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那
展开全文
题意：给你一棵树包含n个顶点，和n-1条边。在这棵树的基础上再加一条边。求树上两个顶点之间的距离。 题解：其实有题意我们很容易想到要求两个顶点之间的LCA,从而间接求解两个顶点之间的最短距离。1.首先我们考虑不做缆车，那就是求dist(x,y)2.我们在考虑做缆车的情况，但是有分两种情况2.1从x走
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
