重工电子论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
查看: 35|回复: 0

[其他] 【LCA模版】

[复制链接]

6

主题

6

帖子

26

积分

新手上路

Rank: 1

积分
26
发表于 2018-6-13 23:26:03 | 显示全部楼层 |阅读模式
本帖最后由 李维强-15级 于 2018-6-15 01:40 编辑

[C++] syntaxhighlighter_viewsource syntaxhighlighter_copycode
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,cnt;
int End[5005],Last[5005],Next[5005],Len[5005],F[5005][20],D[5005],Sum[5005][20];
void add(int x,int y,int z){
	End[++cnt]=y;
	Next[cnt]=Last[x];
	Last[x]=cnt;
	Len[cnt]=z;
}
void DFS(int x){
	D[x]=D[F[x][0]]+1;
	for(int i=1;i<=ceil(log2(D[x]));i++)F[x][i]=F[F[x][i-1]][i-1],Sum[x][i]=Sum[x][i-1]+Sum[F[x][i-1]][i-1];
	for(int i=Last[x];i;i=Next[i]){
		if(End[i]==F[x][0])continue;
		F[End[i]][0]=x;Sum[End[i]][0]=Len[i];
		DFS(End[i]);
	}
}
int LCA(int x,int y){
	if(D[x]<D[y])swap(x,y);
	int k=D[x]-D[y],tot=0;
	for(int i=0;i<=ceil(log2(k));i++)if((1<<i)&k)tot+=Sum[x][i],x=F[x][i];
	if(x==y)return tot;
	k=D[x];
	for(int i=ceil(log2(k));i>=0;i--)if(F[x][i]!=F[y][i])tot+=(Sum[x][i]+Sum[y][i]),x=F[x][i],y=F[y][i];
	return tot+Sum[x][0]+Sum[y][0];
}
int main(){
	int a,b,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);add(b,a,c);
	}
	DFS(1);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",LCA(a,b));
	}
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|cqutlab ( 渝ICP备15004556号

GMT+8, 2018-8-19 07:30 , Processed in 0.087017 second(s), 26 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表