lca板子
2024-10-21 09:11:13
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,q,k;
LL ans,dis[M];
LL f[M][],vis[M],deep[M];
LL first[M],cnt;
struct node{LL to,next,w;}e[M];
void ins(LL a,LL b,LL w){e[++cnt]=(node){b,first[a],w}; first[a]=cnt;}
void insert(LL a,LL b,LL w){ins(a,b,w); ins(b,a,w);}
void dfs(LL x){
vis[x]=;
for(int i=;(<<i)<=deep[x];i++) f[x][i]=f[f[x][i-]][i-];
for(int i=first[x];i;i=e[i].next){
int now=e[i].to;
if(!vis[now]){
deep[now]=deep[x]+;
f[now][]=x;
dis[now]=dis[x]+e[i].w;
dfs(now);
}
}
}
int find(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
int d=deep[x]-deep[y];
for(int i=;(<<i)<=d;i++) if((<<i)&d) x=f[x][i];
if(x==y) return x;
for(int i=;i>=;i--)
if((<<i)<=deep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][];
}
int main(){
int x,y,w;
n=read();
for(int i=;i<n;i++) x=read(),y=read(),w=read(),insert(x,y,w);
dfs();
q=read(); k=read();
for(int i=;i<=q;i++){
x=read(); y=read();
ans=;
int s1=find(x,k),s2=find(y,k);
LL sum1=dis[x]+dis[k]-dis[s1]*;
LL sum2=dis[y]+dis[k]-dis[s2]*;
ans=ans+sum1+sum2;
printf("%lld\n",ans);
}
return ;
}
最新文章
- 【转】bind - DNS 設定
- [转]IIS添加MIME扩展类型及常用的MIME类型列表
- android studio中xml没有提示
- php-jquery-json-3
- 这只是一篇用Markdown写的随记,就是熟悉熟悉MarkDown而已
- oracle merge into 语法
- UVA 821 Page Hopping 网页跳跃(BFS,简单)
- jquery formatCurrency货币格式化处理
- QSerialPort
- 【mysql】关于子查询的一个例子
- 不想当程序员的CEO不是好投资人:小米雷军23年前所写代码曝光
- JavaWeb学习笔记五 会话技术Cookie&;Session
- 软件测试第四次作业—— 性能测试(含JMeter实验)
- kafka 的安装部署
- win8外包公司——技术分享:参数传递
- Excel设置excel打印每页都有表头标题
- Eclipse + PyDev 快捷键
- 删除数据恢复数据语句 Oracle
- webView返回不刷新
- 学习Emmet