[HDU]P2586 How far away?[LCA]
How far away ?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18675 Accepted Submission(s): 7274
Problem Description
There are n houses in the village and some
bidirectional roads connecting them. Every day peole always like to ask like
this "How far is it if I want to go from house A to house B"? Usually
it hard to answer. But luckily int this village the answer is always unique,
since the roads are built in the way that there is a unique simple
path("simple" means you can't visit a place twice) between every two
houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10),
indicating the number of test cases.
For each test case,in the first line there are two numbers
n(2<=n<=40000) and m (1<=m<=200),the number of houses and the
number of queries. The following n-1 lines each consisting three numbers i,j,k,
separated bu a single space, meaning that there is a road connecting house i
and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer
the distance between house i and house j.
Output
For each test case,output m lines. Each
line represents the answer of the query. Output a bland line after each test
case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
Source
Recommend
lcy | We
have carefully selected several similar problems for you: 3486 2874 2888 3234 2818
这道题就是很裸的LCA,主要是练一下倍增,今天考试一道有关LCA的,我用树剖打竟然T了?(感觉效率有保证,不知道是不是数据问题)
可恶啊,打了很久诶,于是就来学习一下倍增。
代码:
//2017.11.7 //lca #include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read(); namespace lys{ ; struct edge{ int to; int next; int w; }e[N*]; ],dis[N][],dep[N],pre[N]; int n,m,cnt; void swap(int &a,int &b){int t=a;a=b;b=t;} void add(int x,int y,int w){ e[++cnt].to=y;e[cnt].next=pre[x];pre[x]=cnt;e[cnt].w=w; e[++cnt].to=x;e[cnt].next=pre[y];pre[y]=cnt;e[cnt].w=w; } void dfs(int node,int deep){ dep[node]=deep; int i,v; ;i<=;i++) anc[node][i]=anc[anc[node][i-]][i-],dis[node][i]=dis[node][i-]+dis[anc[node][i-]][i-]; for(i=pre[node];i;i=e[i].next){ v=e[i].to; ]) continue ; anc[v][]=node; dis[v][]=e[i].w; dfs(v,deep+); } } int lca(int x,int y){ ,i; if(dep[x]<dep[y]) swap(x,y); ;i>=;i--) if(dep[y]<=dep[anc[x][i]]) res+=dis[x][i],x=anc[x][i]; if(x==y) return res; ;i>=;i--) if(anc[x][i]!=anc[y][i]) res+=dis[x][i]+dis[y][i],x=anc[x][i],y=anc[y][i]; ]+dis[y][]; } int main(){ memset(pre,,sizeof pre); int i,u,v,w; n=read(); m=read(); cnt=; ;i<n;i++){ u=read(); v=read(); w=read(); add(u,v,w); } dfs(,); while(m--){ u=read(); v=read(); printf("%d\n",lca(u,v)); } ; } } int main(){ int T=read(); while(T--) lys::main(); ; } inline int read(){ ,ff=; char c=getchar(); '){ ; c=getchar(); } +c-',c=getchar(); return kk*ff; }
最新文章
- 关于在biweb 中安装完成后 首页上方报错问题的解决
- atitit.设计模式(1)--—职责链模式(chain of responsibility)最佳实践O7 日期转换
- UIButton在不同状态下显示不同背景色
- Windows 编 程中的字符串
- DOS 循环读取txt每一行内容
- 华为";128为大整数相加";机试题
- 数据库中的DDL和DML语言
- Impala:新一代开源大数据分析引擎
- javaWEB总结(6):ServletRequest
- Struts文件下载
- SpringMVC 无法访问到指定jsp页面可能的原因
- Spring Boot 配置文件详解
- Ext JS 6开发实例(四) :调整主视图
- [精华][推荐]CAS SSO实现单点登录框架学习源码
- jdk中的简单并发,需要掌握
- Nodejs 安装 on centos7
- 解决docker镜像无法下载的问题
- 七、K3 WISE 开发插件《Update字段级更新触发器 - BOS单审核后反写源单》
- org.apache.catalina.core.StandardWrapperValve invoke的解决办法
- 基于jCOM搭建Java-微软信息桥梁(上)
热门文章
- MySQL学习-数据库设计以及sql的进阶语句
- OpenCV在ARM-linux上的移植过程遇到的问题3---共享库中嵌套库居然带路径【未解决】
- Clover的简单使用
- [集合]Map
- Debian/Ubuntu下安装Apache的Mod_Rewrite模块的步骤分享
- jquery中的插件EChars的使用
- 最长公共子序列(LCS) Medium2
- 【学习总结】快速上手Linux玩转典型应用-第4章-准备工作
- Red Hat Enterprise Linux查看系统版本命令
- c++ Socket客户端和服务端示例版本二