题意:
给你一棵树包含n个顶点,和n-1条边。在这棵树的基础上再加一条边。求树上两个顶点之间的距离。
题解:
其实有题意我们很容易想到要求两个顶点之间的LCA,从而间接求解两个顶点之间的最短距离。
1.首先我们考虑不做缆车,那就是求dist(x,y)
2.我们在考虑做缆车的情况,但是有分两种情况
2.1从x走到u做缆车,dist(x,u)+dist(v,y)
2.2从x走到v做缆车,dist(x,v)+dist(u,y)
综上,ans=min(dist(x,y),dist(x,u)+dist(v,y),dist(x,v)+dist(u,y))
代码:
#include <bits/stdc++.h> using namespace std; const int maxn=3e5+10; int n,qu,root,Dep[maxn],fa[maxn],ans,in[maxn]; vector<int>vec[maxn]; struct node{ int id,dep; }; void bfs(){ int i,id,lenV; node now; queue<node>qu; qu.push({root,0}); while(!qu.empty()){ now=qu.front(),qu.pop();Dep[now.id]=now.dep; lenV=vec[now.id].size(); for (i=0;i<lenV;i++){ id=vec[now.id][i]; qu.push({id,now.dep+1}); } } } int lca(int x,int y){ if(x==y)return x; if(Dep[x]<Dep[y])swap(x,y); while(Dep[x]>Dep[y])x=fa[x]; if(x==y)return x; while(x!=root){ x=fa[x],y=fa[y]; if(x==y)return x; } return root; } int main() { int i,j,k,u,v,x,y; while(scanf("%d",&n)!=EOF){ memset(in,0,sizeof(in)); for (i=1;i<=300000;i++)vec[i].clear(); for (i=n-1;i>=1;i--){ scanf("%d%d",&u,&v); if(u>v)swap(u,v); fa[v]=u,vec[u].push_back(v);in[v]++; } scanf("%d%d",&u,&v); if(u>v)swap(u,v); for (i=1;i<=n;i++){ if(in[i]==0){ root=i;break; } } bfs(); scanf("%d",&qu); while(qu--){ scanf("%d%d",&x,&y); if(x>y)swap(x,y); ans=Dep[x]+Dep[y]-2*Dep[lca(x,y)]; ans=min(ans,Dep[x]+Dep[u]-2*Dep[lca(x,u)]+Dep[v]+Dep[y]-2*Dep[lca(v,y)]); ans=min(ans,Dep[x]+Dep[v]-2*Dep[lca(x,v)]+Dep[u]+Dep[y]-2*Dep[lca(u,y)]); printf("%d\n",ans); } } return 0; }