专栏首页wymHDU 2586 How far away ?(最长公共祖先 LCA模板题)

HDU 2586 How far away ?(最长公共祖先 LCA模板题)

离线版本的思路是:每个点都把与它有关的查询放进它的那个vector里,然后对这棵树进行一次dfs,在dfs的过程中直接得出所有查询的答案,复杂度是O(n+q)。

具体来说,假设有一个查询u,v,当遍历到u的时候,如果v还没有访问,就先不管这个查询;如果v已经访问过了,

则由于进行的是深度优先搜索,当前结点与v的最近公共祖先一定还没有检查过,然而这个最近公共祖先的包含v的子树

一定已经搜索过了,那么这个最近公共祖先一定是v所在集合的祖先

#include <bits/stdc++.h>
using namespace std;

const int maxn=40005;
int f[maxn],head[maxn],dis[maxn],ans[202],vis[maxn];
int tot,n;
struct Edge{
	int u,v,w,next;
};
Edge edge[maxn*2];
vector< pair<int,int> > Q[maxn];
int find(int x)
{
	return f[x]==x?x:x=find(f[x]);
}
void add(int u,int v,int w)
{
	edge[tot].u=u;
	edge[tot].v=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void init()
{
	for(int i=0;i<=maxn;i++)
	Q[i].clear(),f[i]=i,ans[i]=0,dis[i]=0,vis[maxn],head[i]=-1;
	tot=0;
}
void dfs(int u,int d)
{
	dis[u]=d;
	vis[u]=1;
	for(int i=head[u];~i;i=edge[i].next)
	{
		int v=edge[i].v;
		int w=edge[i].w;
		if(!vis[v])
		{
			dfs(v,d+w);
			f[v]=u;
		}
	}
	
	for(int i=0;i<Q[u].size();i++)
	{
		int v=Q[u][i].first;
		int id=Q[u][i].second;
		if(vis[v])
		{
			int lca=find(v);
			ans[id]=dis[u]-dis[lca]+dis[v]-dis[lca];
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		init();
		int q;
		scanf("%d %d",&n,&q);
		for(int i=0;i<n-1;i++)
		{
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		for(int i=0;i<q;i++)
		{
			int u,v;
			scanf("%d %d",&u,&v);
			Q[u].push_back(make_pair(v,i));
			Q[v].push_back(make_pair(u,i));//
		}
		dfs(1,0);
		for(int i=0;i<q;i++)printf("%d\n",ans[i]);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • E旅行商问题

     从1走遍所有点,则必定会重复走很多路,选择从一到最远的一条路只走一边,其他全都要走两遍。

    用户2965768
  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 洛谷P2391 白雪皑皑(并查集)

    题目背景 “柴门闻犬吠,风雪夜归人”,冬天,不期而至。千里冰封,万里雪飘。空中刮起了鸭毛大雪。雪花纷纷,降落人间。 美能量星球(pty 在 spore 上的一个...

    attack
  • 图像处理卷积算法实现

      今天心血来潮,想把传统的卷积算法实现一份不采用各种加速方式,仅优化算法逻辑的纯净版本。 写完发现性能还可以,特发出来分享之,若有博友在此基础上,进行了再次优...

    cpuimage
  • 洛谷P2607 [ZJOI2008]骑士(树形dp)

    题目描述 Z国的骑士团是一个很有势力的组织,帮会中汇聚了来自各地的精英。他们劫富济贫,惩恶扬善,受到社会各界的赞扬。 最近发生了一件可怕的事情,邪恶的Y国发动了...

    attack
  • 用指针函数实现输出若干个学生中成绩最高的

    题目描述:读入n(1 <= n <= 1000)个学生的成绩,成绩都为整数,用指针函数求出若干个学生成绩的最高分。用数组名作为函数参数,指针作为函数返回值。

    小Bob来啦
  • Java中实现找到两个数组交集的2种方法,开发实用

    1、用HashSet实现的解决方法 实例代码如下: public int[] intersection(int[] nums1, int[] nums2) { ...

    用户1289394
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • E旅行商问题

     从1走遍所有点,则必定会重复走很多路,选择从一到最远的一条路只走一边,其他全都要走两遍。

    用户2965768

扫码关注云+社区

领取腾讯云代金券