【牛客】 小A的最短路 （LCA）
原题链接
题意：
给定一棵树，除给定的特殊边边权为0外，其余边权均为1。求两点之间的最短距离。n为3e5
思路：
今天碰到的第一道喜欢的题hhhhhh
题目是一棵树这个条件有点隐蔽直接进行最短路可能并不可行，考虑树上求两点距离的方法，一般就是LCA。
因为存在特殊边，所以节点a和b之间的距离可能有三种情况，一是考虑不经过特殊边，直接从节点a到节点b；二是考虑经过特殊边，这时候就考虑顺序了，设特殊边的两个端点分别是q,w；要么是a-x-y-b,要么是b-x-y-a；三者取min就好了。
代码：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll #define x first #define y second inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f,mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=3e5+100,maxm=3e6+7; const double PI = atan(1.0)*4; vector<int>G[maxn*2]; int n,U,V,m; int dep[maxn],fa[maxn][20]; void dfs(int u){ for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=0;i<G[u].size();i++){ int j=G[u][i]; if(fa[u][0]==j) continue; dep[j]=dep[u]+1; fa[j][0]=u; dfs(j); } } int lca(int a,int b){ if(dep[a]<dep[b]) swap(a,b); for(int k=15;k>=0;k--) if(dep[fa[a][k]]>=dep[b]) a=fa[a][k];///使a,b跳到同一层 if(a==b) return a; for(int k=15;k>=0;k--) if(fa[a][k]!=fa[b][k]) a=fa[a][k],b=fa[b][k]; return fa[a][0]; } int cul(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } int main(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); } dfs(1); U=read(),V=read(),m=read(); while(m--){ int u=read(),v=read(); int minn=min(cul(u,v),cul(u,U)+cul(V,v)); minn=min(minn,cul(u,V)+cul(U,v)); out(minn);puts(""); } return 0; }
