首页 > 代码库 > lca板子
lca板子
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=500010; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,q,k; LL ans,dis[M]; LL f[M][35],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]=1; for(int i=1;(1<<i)<=deep[x];i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(!vis[now]){ deep[now]=deep[x]+1; f[now][0]=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=0;(1<<i)<=d;i++) if((1<<i)&d) x=f[x][i]; if(x==y) return x; for(int i=30;i>=0;i--) if((1<<i)<=deep[x]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int main(){ int x,y,w; n=read(); for(int i=1;i<n;i++) x=read(),y=read(),w=read(),insert(x,y,w); dfs(1); q=read(); k=read(); for(int i=1;i<=q;i++){ x=read(); y=read(); ans=0; int s1=find(x,k),s2=find(y,k); LL sum1=dis[x]+dis[k]-dis[s1]*2; LL sum2=dis[y]+dis[k]-dis[s2]*2; ans=ans+sum1+sum2; printf("%lld\n",ans); } return 0; }
lca板子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。