[cogs1588]距离咨询

发表于 2016-11-11   |   分类于 st , 图论  |  访问: 47 次

题目传送门

题目大意:

给定一棵树,多次查询树上距离

当然有离线的tarjan算法

先求LCA再求距离啥的

但可以拿来练倍增啊

倍增明显更好写

再倍增求LCA的过程中顺便计算一下距离就可以

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int _maxn=40010;
int n,m,fa[_maxn][20],d[_maxn][20],k,dep[_maxn],head[_maxn];
struct e{
	int to,dis,Next;
}edge[_maxn<<1];
int getint(){
	int ans=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')
		ch=getchar();
	while(ch>='0' && ch<='9'){
		ans*=10;
		ans+=ch-'0';
		ch=getchar();
	}
	return ans;
}
void add(int x,int y,int z){
	++k;
	edge[k].Next=head[x];
	edge[k].to=y;
	edge[k].dis=z;
	head[x]=k;
}
void dfs(int x){
	for(int i=1;i<=16;i++){
		if((1<<i)>dep[x])
			break;
		fa[x][i]=fa[fa[x][i-1]][i-1];
		d[x][i]=d[x][i-1]+d[fa[x][i-1]][i-1];
	}
	int v;
	for(int i=head[x];i;i=edge[i].Next){
		v=edge[i].to;
		if(dep[v]==-1){
			fa[v][0]=x;
			d[v][0]=edge[i].dis;
			dep[v]=dep[x]+1;
			dfs(v);
		}
	}
}
int query(int x,int y){
	int ans=0;
	if(dep[x]<dep[y])
		swap(x,y);
	int l=dep[x]-dep[y];
	for(int i=16;i>=0;i--){
		if(l&(1<<i)){
			ans+=d[x][i];
			x=fa[x][i];
		}
	}
	for(int i=16;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			ans+=d[x][i]+d[y][i];
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	if(x!=y)
		ans+=d[x][0]+d[y][0];
	return ans;
}
int main(){
	freopen("dquery.in","r",stdin);
	freopen("dquery.out","w",stdout);
	memset(dep,-1,sizeof(dep));
	char ch;
	int x,y,z;
	n=getint();m=getint();
	for(int i=1;i<=m;i++){
		x=getint();
		y=getint();
		z=getint();
		scanf("%c",&ch);
		add(x,y,z);
		add(y,x,z);
	}
	int q=getint();
	fa[1][0]=dep[1]=d[1][0]=0;
	dfs(1);
	for(int i=1;i<=q;i++){
		x=getint();y=getint();
		printf("%d\n",query(x,y));
	}
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark