思路：计算出所有点到1号点的最短距离，到x号点的最短距离，然后找到一些这样的点，这个点到x点的距离小于到1号点的距离，然后选出这些点中距离1号点最远的点就是结果。
#include <cstdio> #include <cstring> #include <vector> #include <queue> using std::priority_queue; using std::vector; const int MAXN = 2e5+10; struct qnode { int v,c; qnode(int _v = 0, int _c = 0):v(_v),c(_c) {} bool operator <(const qnode &r) const { return c>r.c; } }; struct Edge { int v,cost; Edge(int _v = 0, int _cost = 0):v(_v),cost(_cost) {} }; vector<Edge> E[MAXN]; const int INF = 0x3f3f3f3f; int n,x; //dist[0] ->distA //dist[1] ->distB int dist[2][MAXN]; bool vis[MAXN]; void Dijkstra(int n, int start, int index) { memset(vis,false,sizeof(vis)); for(int i=1; i<=n; i++) dist[index][i]=INF; priority_queue<qnode> que; while(!que.empty()) que.pop(); dist[index][start]=0; que.push(qnode(start,0)); qnode tmp; while(!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u])continue; vis[u]=true; for(int i=0; i<E[u].size(); i++) { int v=E[tmp.v][i].v; int cost=E[u][i].cost; if(!vis[v]&&dist[index][v]>dist[index][u]+cost) { dist[index][v]=dist[index][u]+cost; que.push(qnode(v,dist[index][v])); } } } } void addedge(int u,int v,int w) { E[u].push_back(Edge(v,w)); E[v].push_back(Edge(u,w)); } int main() { int a,b; scanf("%d %d",&n,&x); for(int i = 0; i < n-1; ++i) { scanf("%d %d",&a,&b); addedge(a,b,1); } Dijkstra(n,1,0); Dijkstra(n,x,1); int res = 0; for(int i = 2; i <= n; ++i) { if(dist[0][i] > dist[1][i]) { if(dist[0][i] > res) res = dist[0][i]; } } printf("%d\n",res*2); return 0; }