设$f[i]$表示$i$往上通过一趟公交车能到达的深度最小的祖先，这可以通过将公交车按$lca$深度从小到大排序后用并查集染色得到。

对于每个询问：

$1.x==y$

$ans=0$。

$2.x$是$y$的祖先

交换$x,y$，变成$3$。

$3.y$是$x$的祖先：

在$f$上倍增即可。

$4.x->lca->y$

首先倍增求出一步就能到$lca$的那个点$t$，然后沿着$lca$往下贪心爬一步到达$z$，再加上$z$到$y$的距离。

找$z$的时候，考虑二分查找，那么只需要判断两个点之间是否可以只用一条公交线路到达。

这等价于判断是否有公交线路起点在$t$子树内，终点在$z$子树内，可持久化线段树维护。

时间复杂度$O(n\log^2n)$。

 

#include
     
      #include
      
       using namespace std;const int N=10010,K=15,M=320010;int n,m,Q,i,j,x,y,z,g[N],v[N<<1],nxt[N<<1],ed,G[N],V[N<<1],NXT[N<<1],ED;int p[N],fa[N][K],f[N],d[N],size[N],son[N],st[N],en[N],dfn,q[N],top[N];int T[N],l[M],r[M],val[M],tot;struct E{int x,y,z;}e[N];inline bool cmp(const E&a,const E&b){return d[a.z]
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void ADD(int x,int y){V[++ED]=y;NXT[ED]=G[x];G[x]=ED;}void dfs(int x){  size[x]=1;d[x]=d[f[x]]+1;  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){    f[v[i]]=x;    dfs(v[i]),size[x]+=size[v[i]];    if(size[v[i]]>size[son[x]])son[x]=v[i];  }}void dfs2(int x,int y){  q[st[x]=++dfn]=x;top[x]=y;  if(son[x])dfs2(son[x],y);  for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);  en[x]=dfn;}inline int lca(int x,int y){  for(;top[x]!=top[y];x=f[top[x]])if(d[top[x]]
        
         d[y])return -1;  int t=1;  for(int i=K-1;~i;i--)if(d[fa[x][i]]>d[y])x=fa[x][i],t+=1<
         
          >1;  if(c<=mid)l[y]=ins(l[x],a,mid,c),r[y]=r[x];else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c);  return y;}int ask(int x,int a,int b,int c,int d){  if(c<=a&&b<=d)return val[x];  int mid=(a+b)>>1,t=0;  if(c<=mid)t=ask(l[x],a,mid,c,d);  if(d>mid)t+=ask(r[x],mid+1,b,c,d);  return t;}inline bool check(int x,int y){return ask(T[en[x]],1,n,st[y],en[y])>ask(T[st[x]-1],1,n,st[y],en[y]);}inline int query(int x,int y){  if(st[x]<=st[y]&&en[y]<=en[x])return go(y,x);  if(st[y]<=st[x]&&en[x]<=en[y])return go(x,y);  int z=lca(x,y),t=0;  if(d[fa[x][K-1]]>d[z])return -1;  for(int i=K-1;~i;i--)if(d[fa[x][i]]>d[z])x=fa[x][i],t+=1<
          
           >1)))r=(o=mid)-1;else l=mid+1; o=go(y,up(y,o)); if(o<0)return -1; return t+o+1;}void dfs3(int x){ for(int i=1;i
           
            =d[y];x=F(x))fa[x][0]=y,p[x]=f[x];}int main(){ read(n),read(m),read(Q); for(i=1;i
            
             0)z--; printf("%d\n",z); } return 0;}