/*
变量注释：
q[]数组存储的是边的信息，便于链表使用，next是下一条边，to是指向节点。
head[]数组储存每个节点的当前边。
tot起建立链表的作用。
sheep1、2存储开始节点。
vis表示到达的点，用于找最优解。
定义结构体pos存储BFS时的队列信息，z[]表示正向BFS队列，f[]表示反向BFS队列。pet1、2分别为两个宠物起点。
zp()函数为正push()，zpop为正pop()。对应的f表示的为反。
思路：
读入时建立链表、图。之后从两个宠物出分别BFS，找最优解。
结果：
RQNOJ上测试过8组数据，时间200+ms，最大数据耗时700ms，与其他代码相比较快，但是更长。
错误数据中，有一个答案为1，但是该代码输出为4位数。
另一个答案为88888，输出为9000+。
要求输出的是节点号。
*/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define maxn 1000010
int n;
//bool path[maxn][maxn]; 邻接矩阵版本，放弃
int head[maxn];
int tot=0;
int sheep1,sheep2;
bool zvis[maxn]={0};
bool fvis[maxn]={0};
//邻接链表版本
struct link
{
int to;
int next;
}q[maxn];
struct pos
{
int nowpos;
int step;
}z[maxn],f[maxn],pet1,pet2;
int zl=0,zr=0,fl=0,fr=0;
void zp(pos cs)
{
z[zr++]=cs;
}
void fp(pos cs)
{
f[fr++]=cs;
}
pos zpop()
{
return z[zl++];
}
pos fpop()
{
return f[fl++];
}
void add_edge(int u,int v)
{
q[tot].to=v;
q[tot].next=head[u];
head[u]=tot++;
}
void readdata()
{
/*
邻接矩阵版本 ，放弃
int now,to;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&now,&to);
}
*/
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&v,&u);
add_edge(u,v);
//printf("%d\n",tot);
}
scanf("%d%d",&sheep1,&sheep2);
pet1.nowpos=sheep1;
pet1.step=0;
zvis[sheep1]=1;
zp(pet1);
pet2.nowpos=sheep2;
pet2.step=0;
fvis[sheep2]=1;
fp(pet2);
}
bool zcheck(pos cs)
{
if(zvis[cs.nowpos])return false;
if(fvis[cs.nowpos])
{
printf("%d\n",cs.nowpos);
//while(1);
exit(0);
}
return zvis[cs.nowpos]=true;
}
bool fcheck(pos cs)
{
if(fvis[cs.nowpos])return false;
if(zvis[cs.nowpos])
{
printf("%d\n",cs.nowpos);
//while(1);
exit(0);
}
return fvis[cs.nowpos]=true;
}
pos expand(pos cs,int i)
{
cs.nowpos=q[i].to;
cs.step++;
return cs;
}
void work()
{
while(zl<zr && fl<fr)
{
pos zn=zpop(),fn=fpop();
/*for(int i=0;i<100;i++)
{printf("%d ",q[i].next);}*/
/*printf("%d %d\n",head[zn.nowpos],q[head[zn.nowpos]].next);
printf("%d %d\n",head[fn.nowpos],q[head[fn.nowpos]].next);*/
for(int i=head[zn.nowpos];i!=-1;i=q[i].next)
{
pos zne=expand(zn,i);
if(zcheck(zne))zp(zne);
}
for(int i=head[fn.nowpos];i!=-1;i=q[i].next)
{
//printf("test\n");
pos fne=expand(fn,i);
if(fcheck(fne))fp(fne);
}
}
while(zl<zr && fl>=fr)
{
pos zn=zpop();
for(int i=head[zn.nowpos];i!=-1;i=q[i].next)
{
pos zne=expand(zn,i);
if(zcheck(zne))zp(zne);
}
}
while(fl<fr && zl>=zr)
{
pos fn=fpop();
for(int i=head[fn.nowpos];i!=-1;i=q[i].next)
{
pos fne=expand(fn,i);
if(fcheck(fne))fp(fne);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
readdata();
work();
//while(1);
return 0;
}
有两组数据过不了啊。。。求解求解
var i,n,a,b,pos1,pos2,e,now:longint;
tou,hj,bian:array [1..1000001] of longint;
visit:array[1..1000001] of boolean;
assh:real;
begin
fillchar(hj,sizeof(hj),0);
fillchar(visit,sizeof(visit),false);
readln(n);
e:=0;
for i:= 1 to n-1 do begin
readln(a,b); inc(e); bian[e]:=a; hj[e]:=tou[b]; tou[b]:=e;
end;
readln(pos1,pos2);
now:=tou[pos1];
visit[pos1]:=true;
while (now<>0) do begin
visit[bian[now]]:=true;
now:=tou[bian[now]];
end;
if(visit[pos2]) then begin write(pos2); halt; end;
now:=tou[pos2];
while (now<>0) do begin
if(visit[bian[now]]) then begin write(bian[now]); halt; end;
now:=tou[bian[now]];
end;
end.