10 条题解
-
-1
#include<bits/stdc++.h> using namespace std;
const int MAXN=500000+5; const int MAXM=500000+5;
int head[MAXN]; int father[MAXN]; bool visited[MAXM]; int bianshu;
struct edge { int v,next; }g[2*MAXM];
void addedge(int u,int v) { g[++bianshu].next=head[u]; g[bianshu].v=v; head[u]=bianshu; return; }
queue q; int s; void bfs() { q.push(s); while(!q.empty()) { int ppp=q.front(); q.pop(); for(int i=head[ppp];i;i=g[i].next) { if(!visited[g[i].v]) { visited[g[i].v]=true; father[g[i].v]=ppp; q.push(g[i].v); } } }
}
int path1[MAXN]; int path2[MAXN]; int cntp1,cntp2; int ans; int main() { int n,q; int uu,vv; int a,b; int LCA,a1,a2; scanf("%d%d%d",&n,&q,&s); for(int i=1;i<=n-1;++i) { scanf("%d%d",&uu,&vv); addedge(uu,vv); addedge(vv,uu); } father[s]=s; visited[s]=true; bfs(); for(int i=1;i<=q;++i) { scanf("%d%d",&a,&b); for(int j=a;j!=s;j=father[j]) { path1[++cntp1]=j; } path1[++cntp1]=s; for(int j=b;j!=s;j=father[j]) { path2[++cntp2]=j; } path2[++cntp2]=s; while(path1[cntp1--]==path2[cntp2--]) { ans=path1[cntp1+1]; } printf("%d\n",ans); memset(path1,0,sizeof(path1)); memset(path2,0,sizeof(path2)); cntp1=0; cntp2=0; ans=0; } return 0; }
信息
- ID
- 121
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 661
- 已通过
- 192
- 上传者