国庆集训D1T3 小X的佛光

本文主要是介绍国庆集训D1T3 小X的佛光，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

存双向边要开两倍空间！！！！！

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
const int N=4e5+1000;
int n,q,num;
int nxt[N],to[N],head[N],len;
int dep[N],fa[N][21];
void addedge(int u,int v){ nxt[++len]=head[u]; to[len]=v; head[u]=len; }
void dfs(int v,int dp,int father){dep[v]=dp; fa[v][0]=father;rep(i,1,20) fa[v][i]=fa[fa[v][i-1]][i-1];for(int i=head[v];i!=0;i=nxt[i]){//初始化为-1？？if(to[i]==father) continue;dfs(to[i],dp+1,v);}
}
int lca(int u,int v){if(dep[u]<dep[v]) return lca(v,u);per(i,20,0) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];if(u==v) return v;per(i,20,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}
int main(){scanf("%d%d%d",&n,&q,&num);rep(i,1,n-1){int x,y; scanf("%d%d",&x,&y);addedge(x,y); addedge(y,x);}dfs(1,1,0);while(q--){int a,b,c,fab,fac,fbc,cent;scanf("%d%d%d",&a,&b,&c);fab=lca(a,b); fac=lca(a,c); fbc=lca(b,c);if(dep[fab]>dep[fac]) cent=fab; else cent=fac;if(dep[cent]<dep[fbc]) cent=fbc;printf("%d\n",dep[cent]+dep[b]-dep[lca(cent,b)]*2+1);}return 0;
}

这篇关于国庆集训D1T3 小X的佛光的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---