题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3195

题意: 给出一棵 n 个节点的带边权的树, 有 q 组形如 x, y, z 的询问, 输出 x, y, z之间的最短路径.

思路: 在纸上画下不难发现 x, y, z之间的最短路径就是 x, y, z 两两之间的最短路径和的一半.

我们可以通过 lca 模板求出 x, y, z 两两之间的最短路径, 然后再算下 x, y, z三点之间的最短路径即可.

这题应该是用 RMQ 在线比较好写一点, 用 tarjan 的话记录路径有点麻烦.

代码:

 #include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std; const int MAXN = 5e4 + ;
struct node{
int v, w, next;
}edge[MAXN << ]; int dp[MAXN << ][];
int ver[MAXN << ], deep[MAXN << ], first[MAXN];
int dis[MAXN], head[MAXN], vis[MAXN], indx, ip; inline void init(void){
memset(vis, , sizeof(vis));
memset(head, -, sizeof(head));
indx = ;
ip = ;
} void addedge(int u, int v, int w){
edge[ip].v = v;
edge[ip].w = w;
edge[ip].next = head[u];
head[u] = ip++;
} void dfs(int u, int h){
vis[u] = ;
ver[++indx] = u;
deep[indx] = h;
first[u] = indx;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].v;
if(!vis[v]){
dis[v] = dis[u] + edge[i].w;
dfs(v, h + );
ver[++indx] = u;
deep[indx] = h;
}
}
} void ST(int n){
for(int i = ; i <= n; i++){
dp[i][] = i;
}
for(int j = ; ( << j) <= n; j++){
for(int i = ; i + ( << j) - <= n; i++){
int x = dp[i][j - ], y = dp[i + ( << (j - ))][j - ];
dp[i][j] = deep[x] < deep[y] ? x : y;
}
}
} int RMQ(int l, int r){
int len = log2(r - l + );
int x = dp[l][len], y = dp[r - ( << len) + ][len];
return deep[x] < deep[y] ? x : y;
} int LCA(int x, int y){
int l = first[x], r = first[y];
if(l > r) swap(l, r);
int pos = RMQ(l, r);
return ver[pos];
} int main(void){
bool flag = false;
int n, q, x, y, z;
while(~scanf("%d", &n)){
if(flag) puts("");
flag = true;
init();
for(int i = ; i < n; i++){
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, z);
addedge(y, x, z);
}
dis[] = ;
dfs(, );
ST( * n - );
scanf("%d", &q);
while(q--){
scanf("%d%d%d", &x, &y, &z);
int lca1 = LCA(x, y);
int lca2 = LCA(x, z);
int lca3 = LCA(y, z);
int sol1 = dis[x] + dis[y] - * dis[lca1];
int sol2 = dis[x] + dis[z] - * dis[lca2];
int sol3 = dis[y] + dis[z] - * dis[lca3];
printf("%d\n", (sol1 + sol2 + sol3) >> );
}
}
return ;
}

最新文章

  1. Jetty 的工作原理以及与 Tomcat 的比较
  2. Checkpoint--与lazy writer区别
  3. ios反射
  4. PowerDesigner生成的ORACLE 建表脚本中去掉对象的双引号,设置大、小写
  5. 根据identifier从StoryBoard中获取对象,UIButton的图片文件位置
  6. EF5修改edmx表结构保存后不自动更新tt (转)
  7. Eric的第一天
  8. Python3.6_x86通过FFpmeg获取视频或音频的时长和分辨率
  9. 阿里云服务器(Windows)如何下载文件
  10. 正益移动推出新产品正益工作 实现PaaS+SaaS新组合
  11. 【转】win2008 中iis7设置404页面但返回状态200的问题解决办法
  12. Codeforces 765F Souvenirs 线段树 + 主席树 (看题解)
  13. 简单了解weblogic配置文件
  14. 10享元模式Flyweight
  15. mongoDB 的介绍
  16. WPF实现DoEvents
  17. 浅谈js设计模式 — 命令模式
  18. 报错:System.NotSupportedException: LINQ to Entities does not recognize the method
  19. jenkins持续集成python cases
  20. CentOS随笔 - 6.CentOS7安装Git服务器

热门文章

  1. Visual C++中min()和max()函数的使用
  2. Winform中的dataGridView添加自动编号
  3. Python基础-random模块及随机生成11位手机号
  4. 幻想乡三连A:五颜六色的幻想乡
  5. 使用UIBezierPath添加投影效果
  6. 随机数 while循环 do while循环 for循环
  7. 【转】 Pro Android学习笔记(四三):Fragment(8):再谈Transaction和管理器
  8. JBOSS AS 5.X/6.X 反序列化漏洞(CVE-2017-12149)复现
  9. 异常:Project configuration is not up-to-date with pom.xml解决方案
  10. Mybaits整合Spring自动扫描 接口,Mybaits配置文件.xml文件和Dao实体类