【hihocoder - offer编程练习赛60 C】路径包含问题(LCA,树上倍增)_给出一棵n个节点的树,节点编号为1-n(根节点编号为1),每一个节点作为根节点与他所-程序员宅基地

技术标签: 最近公共祖先  HihoCoder  

题干:

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一棵N的节点的树,节点编号1~N,并且1号节点是根节点。  

小Hi会反复询问小Ho一个问题:给定两个节点a和b,有多少对节点c和d满足c < d且c到d的路径包含完整的a到b的路径?

你能帮帮小Ho吗?

输入

第一行包含两个数N和M,依次是节点总数和问题总数。  

第2~N行每行包含两个整数u和v,代表u是v的父节点。  

以下M行每行包含两个整数a和b,代表一个问题。

对于30%的数据,1 ≤ N, M ≤ 1000

对于100%的数据,1 ≤ N, M ≤ 100000

输出

对于每个问题输出一个整数,代表答案。

样例输入

7 2 
1 2  
1 3  
2 4  
2 5  
3 6  
3 7  
2 3  
2 4

样例输出

9  
6

解题报告:

  跑半遍LCA,到他俩深度相同的时候停止。然后判断是否在同一条链上,分别返回不同的答案就行了。注意在同一条链的时候,不能用u和v的,需要用u(深度大的)的和对应链上dep[v]+1的那个点的。(来看几发错误代码)

错误代码1:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
int fa[MAX][33],dep[MAX],sum[MAX];
int n,m;
vector<int> vv[MAX];
void dfs(int cur,int rt) {
	dep[cur] = dep[rt]+1;
	sum[cur] = 1;
	for(int i = 1; i<=31; i++) {
		fa[cur][i] = fa[fa[cur][i-1]][i-1];
	}
	int sz = vv[cur].size();
	for(int i = 0; i<sz; i++) {
		int v = vv[cur][i];
		if(v == rt) continue;
		dfs(v,cur);
		sum[cur] += sum[v];
	}
}
int lca(int u,int v) {
	
	if(dep[u] < dep[v]) swap(u,v);
	ll ans1 = 1LL*sum[u] * (n - sum[v] + (sum[v]-sum[u]));
	ll ans2 = 1LL*sum[u] * sum[v];
	int dc = dep[u] - dep[v];
	for(int i = 0; i<=31; i++) {
		if(dc>>i & 1) u = fa[u][i];
	}
	if(u == v) {
		return ans1;
	}
	else return ans2;
	for(int i = 31; i>=0 && u != v ; i--) {
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	int res = fa[u][0];//u和v的最近公共祖先.
	 
}
int main()
{
	cin>>n>>m;
	for(int u,v,i = 1; i<=n-1; i++) {
		scanf("%d%d",&u,&v);
		fa[v][0] = u;
		vv[u].pb(v);
		vv[v].pb(u);
	}
	dfs(1,0);
	while(m--) {
		int u,v;
		cin>>u>>v;
		cout << lca(u,v) <<endl;
	}
	return 0 ;
 }

错误代码2:

ll lca(int u,int v) {
	
	if(dep[u] < dep[v]) swap(u,v);
	//ll ans1 = (n - sum[v] + (sum[v]-sum[u]));
	ll sumu = sum[u] ,sumv = sum[v];
	int dc = dep[u] - dep[v];
	for(int i = 31; i>=0; i--) {
		//if(dc>>i & 1) u = fa[u][i];
		if(dep[u]-1 != dep[v]) {
			u = fa[u][i];
		} 
	}
	if(fa[u][0] == v) {//说明在一条链上 
		return sumu*(n-sum[u]);
	}
	else return sumu*sumv;
	for(int i = 31; i>=0 && u != v ; i--) {
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	int res = fa[u][0];//u和v的最近公共祖先.
}

错误代码3:

ll lca(int u,int v) {
	
	if(dep[u] < dep[v]) swap(u,v);
	//ll ans1 = (n - sum[v] + (sum[v]-sum[u]));
	ll sumu = sum[u] ,sumv = sum[v];
	int dc = dep[u] - dep[v];
	for(int i = 31; i>=0; i--) {
		//if(dc>>i & 1) u = fa[u][i];
		if(dep[u] < dep[v]) {
			u = fa[u][i];
		} 
	}
	if(fa[u][0] == v) {//说明在一条链上 
		return sumu*(n-sum[u]);
	}
	else return sumu*sumv;
	for(int i = 31; i>=0 && u != v ; i--) {
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	int res = fa[u][0];//u和v的最近公共祖先.
}

错误代码4:

ll lca(int u,int v) {
	if(dep[u] < dep[v]) swap(u,v);
	ll sumu = sum[u] ,sumv = sum[v];
	for(int i = 31; i>=0 && dep[v] + 1 <= dep[u]; i--) {
		if(dep[fa[u][i]] < dep[v]) {
			u = fa[u][i];
		} 
	}
	if(fa[u][0] == v) {//说明在一条链上 
		return sumu*(n-sum[u]);
	}
	else return sumu*sumv;
}

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
int fa[MAX][33],dep[MAX],sum[MAX];
int n,m;
vector<int> vv[MAX];
void dfs(int cur,int rt) {
	dep[cur] = dep[rt]+1;
	sum[cur] = 1;
	for(int i = 1; i<=31; i++) {
		fa[cur][i] = fa[fa[cur][i-1]][i-1];
	}
	int sz = vv[cur].size();
	for(int i = 0; i<sz; i++) {
		int v = vv[cur][i];
		if(v == rt) continue;
		dfs(v,cur);
		sum[cur] += sum[v];
	}
}
ll lca(int u,int v) {
	if(dep[u] < dep[v]) swap(u,v);
	ll sumu = sum[u] ,sumv = sum[v];
	for(int i = 31; i>=0 && dep[v] + 1 <= dep[u]; i--) {
		if(dep[fa[u][i]] < dep[v]) {
			u = fa[u][i];
		} 
	}
	if(fa[u][0] == v) {//说明在一条链上 
		return sumu*(n-sum[u]);
	}
	else return sumu*sumv;
}
int main()
{
	cin>>n>>m;
	for(int u,v,i = 1; i<=n-1; i++) {
		scanf("%d%d",&u,&v);
		fa[v][0] = u;
		vv[u].pb(v);
		vv[v].pb(u);
	}
	dfs(1,0);
	while(m--) {
		int u,v;
		scanf("%d%d",&u,&v);//cin>>u>>v;
		cout << lca(u,v) <<endl;
	}
	return 0 ;
 }

总结:

  另外注意一下,,,对于一棵树,dep值大的是在下面啊(远离根),别想反了。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41289920/article/details/87118591

智能推荐

Hexo博客主题安装和优化(二)_hexo matery设置雪花飘落-程序员宅基地

文章浏览阅读1.4k次,点赞2次,收藏14次。一、Hexo自定义 —晚枫博客—1. 动态标题打开博客主题文件夹,路径:themes/matery/layout/layout.ejs,在对应位置添加如下代码:<script type="text/javascript"> var OriginTitile = document.title, st; document.addEventLis..._hexo matery设置雪花飘落

tomcat session管理_tomcat session管理页面-程序员宅基地

文章浏览阅读248次。最近有空看了一下tomcat 6源码里面对session管理的实现,现在写下来,以供后考,也希望能对对此感兴趣的朋友有所提示。 闲话少说,先贴一下tomcat6的component层次图(此图来自tomcat doc) Server 就是一个servlet container _tomcat session管理页面

FPGA小白的第一篇博客-程序员宅基地

文章浏览阅读410次。今天是2015年9月22日,我得记住这一天,从今天开始,笔者正式开始FPGA的板级学习,希望早日成为熟练的设计开发者_fpga小白

小经验_chmod: 无法创建符号链接-程序员宅基地

文章浏览阅读4.5k次。1.一个文件夹删不掉,是权限问题,chmod 777 xxx。类似的,根目录下的root文件夹不能访问,也是权限问题。2.serial port terminal(linux下串口终端) CompizConfig(花样)3.source insight安装,得先装wine.4.删除非空文件夹,rm -rf xxx5.arm-linux-gcc -v查看arn-_chmod: 无法创建符号链接

OC----synthesize 关键字_oc synthesize-程序员宅基地

文章浏览阅读998次。@synthesize 关键字6.1 问题: setter, getter的实现也是没有什么任何技术含量6.2 作用: 自动生成getter、setter方法的实现.6.3 语法: @synthesize @property名称; 如: @interface Person : NSObject{ int _age; } @property int age;..._oc synthesize

LWN:Fedora里的fstrim-程序员宅基地

文章浏览阅读827次。关注了就能看到更多这么棒的文章哦~Fedora and fstrimByJake EdgeDecember 31, 2019原文来自:https://lwn.net/Articles/..._fstrim 服务

随便推点

day14_Python基础内容—数据持久化、文件操作、数据持久化方法_每次运行程序输入一个学生的信息怎么回事-程序员宅基地

文章浏览阅读365次。Python学习第14天。学习内容:数据持久化、文件操作、数据持久化方法。一、数据持久化问题1:什么是数据持久化?为什么要持久化?计算机存储空间分为:运行内存和磁盘两种。程序中产生的数据默认都是保存在运行内存中,存储在运行内存中的数据在程序结束后会自动销毁。如果将数据存储到磁盘中,那么数据除非手动删除或者磁盘损坏,否则会一直存在,实现了数据的持久保存,存储在磁盘中的数据可以反复使用。磁盘存储数据的基本单位是文件。数据持久化指的就是将程序中的数据以文件的形式保存到磁盘中。为什么要持久化? _每次运行程序输入一个学生的信息怎么回事

linux安装maven-程序员宅基地

文章浏览阅读76次。1、下载maven包apache-maven-3.3.9-bin.tar.gz2、创建目录mkdir -p/usr/local/maven3、拷贝安装包到指定路径cpapache-maven-3.3.9-bin.tar.gz/usr/local/maven4、解压tar -zxvf apache-maven-3.2.5-bin.tar.gzmv apach..._linux安装maven 3.2.5

机器学习应用之WebShell检测_webshell-master-程序员宅基地

文章浏览阅读6.4k次。本文主要参考自兜哥的《Web安全之机器学习入门》前段时间在研究WebShell的检测查杀,然后看到兜哥的著作中提到的几个机器学习算法中也有实现WebShell检测的,主要有朴素贝叶斯分类、K邻近算法、图算法、循环神经网络算法等等,就一一试试看效果吧。Python中的几个机器学习的库1、numpy:安装:pip install --user numpy2、SciPy:_webshell-master

MySQL调优之索引匹配方式及索引种类_索引包含( )模式匹配的查询-程序员宅基地

文章浏览阅读1.3k次。索引匹配方式下面举例皆在索引 idx(name,age,pos)建立前提下全值匹配全值匹配指的是和索引中的所有列进行匹配匹配最左前缀只匹配前面的几列匹配列前缀可以匹配某一列的值的开头部分比如:select * from staffs where name like ‘J%’;这个语句可以利用到用name建立的索引进行查找。但是如果是 select * from staffs where name like ‘%J%’;就无法用到。匹配范围值可以查找某一个范围的数据比如:explain_索引包含( )模式匹配的查询

Unity给力插件之ShaderForge(一)-程序员宅基地

文章浏览阅读597次。这是一个用来制作shader的插件,也是一个很好的学习shader的工具。这个插件上手很容易,但是要用它来制作理想的Shader,需要下点功夫。这儿先列举出基础知识,以及我的一些实践。以后我还会继续学习并记录更多的内容。一、基本操作:    1)、截断连线:按住alt并右键   2)、框选:按住alt键并框选   3)、对于不认识的节点,右键选择what,出现API官网,可选..._shaderforge遮罩

长东应用 - 流程标题的高级定制、应用换肤与应用预览_流程标题是什么意思-程序员宅基地

文章浏览阅读122次。长东应用拟定在今年12月份发布,这是一款完全免费的高度自由定制的个人单机软件。本文主要介绍流程标题的高级定制、应用自由换肤以及应用发布前的预览功能。目录应用换肤与预览流程标题应用换肤与预览在自定义应用中,右键待发布的app,选择个性化设置。新建个性化设置,系统默认提供六种默认样式,分别为:暗夜精灵、挪威森林、铁血丹心、紫气东来、粉色回忆、酒醉探戈。也可以根据选项自由定制应用内的背景色、字体颜色,可点击上方预览按钮,查看效果。(1)预览 - 暗夜精灵效果(2_流程标题是什么意思

推荐文章

热门文章

相关标签