HDU 2586 How far away ?(LCA在线算法实现)
2024-08-28 07:55:52
http://acm.hdu.edu.cn/showproblem.php?pid=2586
题意:
给出一棵树,求出树上任意两点之间的距离。
思路:
这道题可以利用LCA来做,记录好每个点距离根结点的距离,然后只要计算出两点的LCA,这样一来答案就是distance[u]+distance[v]-2distance[LCA]。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pll;
const int INF = 0x3f3f3f3f;
const int maxn=+; int n, m;
int num;
int tot;
int head[maxn];
int vis[maxn];
int ver[*maxn];
int deep[*maxn];
int dir[maxn];
int first[maxn];
int dp[*maxn][]; struct node
{
int v,w;
int next;
}e[*maxn]; void addEdge(int u, int v, int w)
{
e[num].v=v;
e[num].w=w;
e[num].next=head[u];
head[u]=num++;
} void dfs(int u, int dep)
{
vis[u]=;
ver[++tot]=u; //遍历序列
first[u]=tot; //结点第一次出现位置
deep[tot]=dep; //深度
for(int i=head[u];i!=-;i=e[i].next)
{
if(!vis[e[i].v])
{
int v=e[i].v, w=e[i].w;
dir[v]=dir[u]+w; //距离
dfs(v,dep+);
ver[++tot]=u; //回溯
deep[tot]=dep;
}
}
} 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 a=dp[i][j-],b=dp[i+(<<(j-))][j-];
dp[i][j]=deep[a]<deep[b]?a:b;
}
} int RMQ(int L, int R)
{
int k=;
while((<<(k+))<=R-L+) k++;
int a=dp[L][k], b=dp[R-(<<k)+][k];
return deep[a]<deep[b]?a:b;
} int LCA(int u, int v)
{
int x=first[u], y=first[v]; //查找出他最先出现的地方
if(x>y) swap(x,y);
int res=RMQ(x,y); //查询出的是他祖先的下标
return ver[res];
} int main()
{
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
num=; tot=;
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addEdge(u,v,w);
addEdge(v,u,w);
}
dir[]=;
dfs(,);
ST(*n-);
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
int lca=LCA(u,v);
printf("%d\n",dir[u]+dir[v]-*dir[lca]);
}
}
return ;
}
最新文章
- 创建用资源管理器打开FTP位置
- CentOS7:配置SVN服务器
- 父窗口,子窗口之间的JS";通信";方法
- 每天一个小算法(matlab armijo)
- Linux +apache+fastcgi运行c/c++
- cygwin设置中文
- hdu 5311 Hidden String(find,substr)
- 计算机程序的思维逻辑 (91) - Lambda表达式
- Spring【DAO模块】就是这么简单
- How to work with my desktop and laptop
- 《java入门第一季》之UDP协议下的网络编程详解
- thymeleaf(二)
- gispro试用版账户注册
- C# &; ASP.NET Core 入门官方资料汇总
- _gift
- PostgreSQL+pgpool-II复制方案
- 富文本(wangEditor框架)的使用教程
- bzoj千题计划170:bzoj1968: [Ahoi2005]COMMON 约数研究
- HTML:减少页面加载时间的方法
- 左连接去重(objec)
热门文章
- Tensorflow(二)
- windows server r2 搭建 ftp服务器
- Tomcat重启session失效
- [LeetCode] 190. Reverse Bits_Easy tag: Bit Manipulation
- matplotlib —— 调整坐标轴
- iOS开发--底部按钮和应用图标显示未读消息
- 大神的博客地址liferay
- uva11865 朱刘算法+二分
- Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) Volume 5. Dynamic Programming
- Python 成对处理数据 zip()