第一道LCA

 

#include

<

stdio.h

>

#include

<

string

.h

>

#define

N 10001

int

unionset[N],visit[N];

int

main()

{

int

T,n,a,b,i;

scanf(

"

%d

"

,

&

T);

while

(T

--

)

{

scanf(

"

%d

"

,

&

n);

for

(i

=

1

;i

<=

n;i

++

)

//

init it

{

unionset[i]

=

i;

visit[i]

=

0

;

}

for

(i

=

1

;i

<

n;i

++

)

{

scanf(

"

%d%d

"

,

&

a,

&

b);

unionset[b]

=

a;

}

scanf(

"

%d%d

"

,

&

a,

&

b);

/*

find the root

*/

visit[a]

=

1

;

a

=

unionset[a];

while

(a

!=

unionset[a])

{

a

=

unionset[a];

visit[a]

=

1

;

}

while

(b

!=

unionset[b])

{

if

(visit[b])

break

;

b

=

unionset[b];

}

printf(

"

%d\n

"

,b);

}

return

0

;

}