凛冬将至

Description

维斯特洛大陆的原住民是森林之子,他们长得如孩童一般,善于使用石器,威力值35,用树叶树枝作为衣物,在森林里繁衍生息,与万物和平相处。他们会使用古老的魔法(比如绿之视野),威力值55。后来先民从维斯特洛大陆架登陆,凭借手中的青铜兵器和战马大举入侵,威力值分别是35和55。森林之子凭借魔法顽强抵抗,并冒险利用龙晶制造出了一个神奇的强悍的物种——异鬼,威力值60。双方持久不下之时签订了和平协议,先民占据了维斯特洛大陆,森林之子只保有森林。

七大王国如火如荼兴起之时,在遥远海洋的另一端,一个神秘的家族悄然兴起——坦格利安家族。此家族拥有三条巨龙,威力值90+,经过一个世纪的备战,在领导者伊耿一世的带领下乘龙入侵维斯特洛大陆。

借助龙的力量,伊耿一世很快统一了维斯特洛的七大王国,建立了空前强大的坦格利安王朝,像所有外来入侵者一样,坦格利安家族摒弃了龙的信仰开始信仰七神,并且将龙由放养改为圈养,再加上坦格利安家族为了保持血统纯正,实行近亲婚姻,生出来的继承者精神病人越来越多,这导让坦格利安王朝开始了眼花缭乱的花样作死之旅。

众(wo)所(xia)周(che)知(de),当凯特琳·徒利得知自己女儿艾莉亚逃到赫伦堡后,非常担心女儿的安全。假设维斯特洛大陆共有n个城市,共有n−1条双向道路把这n个城市连接起来。也就是说这是一棵树。凯特琳想尽快临冬城赶到赫伦堡。除了已知的n-1条边外,凯特琳还知道一条额外的秘密路径(也是双向的):端点是是城市x和城市y,路径长度是z。现在想考考寒假过后的你有没有刷过题,问你Q个问题,每个问题给出临冬城(凯特琳所在城市)和赫伦堡(艾莉亚所在城市)的坐标,请你告诉凯特琳从临冬城到赫伦堡的最短路径长度是多少?

Input

第一行一个整数n(1≤n≤100000)。

以下n−1行描述一颗树,每行u,v,w表示一条从u到v长为w的路径,u!=v。

下一行三个整数x,y,z,意义如题(1≤x,y≤n,x!=y)。

下一行一个整数Q(100000)。

以下Q行两个数字U,V代表临冬城和赫伦堡的坐标。

1≤w,z≤10000

Output

对每次询问输出从临冬城到赫伦堡的最短路径长度。

题目中所描述的是一颗

这里再提一下树的特点:

①每个点都联通

②不含圈

③n阶树有n-1条边

PS:特别的是,具备以上任何两个特点可推出第三个

要注意求树上两点的距离不能最短路算法,一般用LCA(只会这个

该题在树的基础上另加了一条边 只需要分情况讨论这条边对原有树的影响即可

故该题解法:裸LCA+分类讨论

ACODE:

//
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<queue>
#include<utility>
#include<vector>
#define lson l , m , rt << 1
#define rson m+1 , r , rt << 1 | 1
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const double pi = 3.1415926535;
const double eps = 1e-;
const int MX = 1e5 + ;
const int maxbit = ;
const double val = pi/180.0;
const int INF = 0x3f3f3f3f;
struct edge
{
int to;
int val;
};
int father[MX][maxbit];
int depth[MX];
int dis[MX];
int lg[MX];
vector<edge> G[MX];
void dfs(int nowp,int fa)
{
depth[nowp] = depth[fa] + ;
father[nowp][] = fa;
for(int j = ;j <= lg[depth[nowp]] + ;++j)
{
father[nowp][j] = father[father[nowp][j-]][j-];
}
for(int i = ;i < G[nowp].size();++i)
{
edge e = G[nowp][i];
if(e.to != fa)
{
dis[e.to] = dis[nowp] + e.val;
dfs(e.to,nowp);
}
}
}
int lca (int u,int v)
{
if(depth[u] < depth[v]) swap(u,v);
while(depth[u] != depth[v])
u = father[u][lg[depth[u] - depth[v]]];
if(u == v) return u;
for(int j = lg[depth[u]];j >= ;--j)
{
if(father[u][j] != father[v][j]){
u = father[u][j];
v = father[v][j];
}
}
return father[u][];
}
//对大常数的优化
void init()
{
lg[] = -;
for(int i = ;i < MX;++i) lg[i] = lg[i >> ] + ;
}
int main(int argc, char const *argv[])
{
int n;
int u,v,w;
init();//记得初始化
scanf("%d",&n);
for(int i = ;i <= n-;++i)
{
scanf("%d%d%d",&u,&v,&w);
//邻接表建图
G[u].push_back({v,w});
G[v].push_back({u,w});
}
dfs(,);
scanf("%d%d%d",&u,&v,&w);
int m;
scanf("%d",&m);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
//三种情况
int p = lca(x,y);
int ans = (dis[x] - dis[p]) + (dis[y] - dis[p]); int p1 = lca(x,u);
int p2 = lca(y,v);
int alt1 = (dis[x] - dis[p1]) + (dis[u] - dis[p1]);
int alt2 = (dis[y] - dis[p2]) + (dis[v] - dis[p2]);
ans = min(ans,alt1 + alt2 + w); p1 = lca(x,v);
p2 = lca(y,u);
alt1 = (dis[x] - dis[p1]) + (dis[v] - dis[p1]);
alt2 = (dis[y] - dis[p2]) + (dis[u] - dis[p2]);
ans = min(ans,alt1 + alt2 + w); printf("%d\n",ans);
}
return ;
}

以后千万不能带个错误的LCA板子了

最新文章

  1. git flow工作流实际项目实践
  2. 疯狂Android讲义 - 学习笔记(六)
  3. [ASE][Daily Scrum]12.12
  4. iOS开发-完整学习路线图
  5. 一台机子上运行使用不同Java版本的多个tomcat
  6. Spring的线程池ThreadPoolTaskExecutor使用案例
  7. ITEM 2 MAC OSX 功能略强大的终端
  8. npm不能安装任何包,报错:npm WARN onload-script failed to require onload script npm-autoinit/autoinit及解决方法
  9. node.js系列(实例):原生node.js实现接收前台post请求提交数据
  10. 使用crontab,让linux定时执行shell脚本
  11. C++实现双链表
  12. min-max容斥
  13. Base64图片转Blob对象
  14. JS中navigator对象详解
  15. eth
  16. 使用vue-cli快速搭建大型单页应用
  17. raiDrive添加坚果云
  18. ios7新特性--1
  19. sphinx 配置文件全解析(转)
  20. Spring-导入和混合配置

热门文章

  1. [luogu2312] 解方程
  2. 《Java程序设计》第12周课堂实践总结
  3. 初识TCP/IP协议
  4. no.random.randn
  5. SVN 客户端使用
  6. java的@PostConstruct注解
  7. 执行Import-SPWeb报错的解决办法
  8. Oracle cursors 游标 for循环遍历
  9. UML基础—结构和组成
  10. jQuery----获取兄弟元素的方法