hdu2586倍增lca
2024-09-04 06:58:46
求距离
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f; struct edge{
int to,Next,w;
}e[N];
int dis[N],father[][N],depth[N];
int cnt,head[N],value[N];
void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].Next=head[u];
head[u]=cnt++;
}
void dfs(int u,int f)
{
father[][u]=f;
for(int i=head[u];~i;i=e[i].Next)
{
int To=e[i].to;
if(To!=f)
{
dis[To]=dis[u]+e[i].w;
depth[To]=depth[u]+;
dfs(To,u);
}
}
}
void init(int n)
{
depth[]=;
dis[]=;
dfs(,-);
for(int i=;i<;i++)
for(int j=;j<=n;j++)
father[i][j]=father[i-][father[i-][j]];
}
int lca(int x,int y)
{
if(depth[x]>depth[y])swap(x,y);
for(int i=;i<;i++)
if((depth[y]-depth[x])>>i&)
y=father[i][y];
if(x==y)return x;
for(int i=;i>=;i--)
{
if(father[i][x]!=father[i][y])
{
x=father[i][x];
y=father[i][y];
}
}
return father[][x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int t,n,m;
cin>>t;
while(t--)
{
cin>>n>>m;
cnt=;
memset(head,-,sizeof head);
for(int i=; i<n; i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
init(n);
while(m--)
{
int a,b;
cin>>a>>b;
cout<<dis[a]+dis[b]-*dis[lca(a,b)]<<endl;
}
}
return ;
}
/******************** ********************/
最新文章
- DNS拾遗(一)
- PL/SQL不支持64位Oracle Client 解决办法
- 分享jstl实现分页,类似百度分页
- 号外号外:9月13号《Speed-BI云平台案例实操--十分钟做报表》开讲了
- Android中直播视频技术探究之---摄像头Camera视频源数据采集解析
- Data Flow ->;>; Merge
- 点线图中的A*算法
- C#的同步和异步调用方法
- sql - 复制表
- JS对象与json字符串格式
- 利用WebBrowser实现Web打印的分析
- 在线的代码托管平台 coding.net ===中国扩展版github
- ueditor编辑器使用总结
- app 性能
- Oracle12c中配置实例参数和修改容器数据库(CDB)及可插拔数据库(PDB)
- 【剑指offer】字符串替换
- Java的OOP三大特征之一——多态
- ksoap2调用webservice传递参数丢失
- wordpress 使用less 样式无法及时刷新
- 215. Kth Largest Element in an Array(QuickSort)