#include #include typedef struct cvor { int br; struct cvor *l, *d; } cvor; void razmak( char c, int n ) { for( int i = 0; i < n; i ++ ) putchar( c ); } void vizuelniPrikaz_( cvor *koren, int nivo ) { if( !koren ) { razmak('\t', nivo ); puts("~"); } else { vizuelniPrikaz_( koren -> d, nivo + 1 ); razmak('\t', nivo ); if( koren -> l ) printf("%d\n", koren -> br ); else printf("%d\n", koren -> br ); vizuelniPrikaz_( koren -> l, nivo + 1 ); } } void vizuelniPrikaz( cvor *koren ) { vizuelniPrikaz_( koren, 0 ); } cvor* novi(int x){ cvor * c = (cvor *)malloc(sizeof(cvor)); c->br = x; c->l = c->d = NULL; return c; } cvor * nadji(cvor * koren, int c){ if(koren ==NULL) return NULL; if(koren->br == c) return koren; cvor * l = nadji(koren->l,c); if(l) return l; return nadji(koren->d,c); } void dodaj(cvor * koren, int c , int levi ,int desni){ cvor * centar = nadji(koren,c); if(levi != 0) centar->l = novi(levi); if(desni != 0) centar->d = novi(desni); } cvor * ucitaj(){ int x, levi, desni; scanf("%d",&x); cvor * koren = novi(x); scanf("%d",&x); while(x) { scanf("%d%d",&levi, &desni); dodaj(koren,x,levi,desni); scanf("%d",&x); } return koren; } int nadjiPut(cvor * koren,int * niz,int x,int index){ if(koren == NULL) return 0; if(koren->br == x) {niz[index] = koren->br; return 1;} if(nadjiPut(koren->l,niz,x,index+1)) {niz[index] = koren->br; return 1;} if(nadjiPut(koren->d,niz,x,index+1)) {niz[index] = koren->br; return 1;} return 0; } int main() { cvor *koren = ucitaj(); vizuelniPrikaz(koren); int n; scanf("%d",&n); int * koraciPrvog = (int *)malloc(100*sizeof(int)); int * koraciDrugog = (int *)malloc(100*sizeof(int)); while(n--) { int x,y; scanf("%d%d",&x,&y); if(koren->br == x || koren->br == y){ printf("Nemaju zajednickog\n"); continue;} for(int i = 0; i<100; i++) koraciPrvog[ i ] = koraciDrugog[ i ] = 0; nadjiPut(koren,koraciPrvog,x,0); nadjiPut(koren,koraciDrugog,y,0); //for(int i = 0 ; i<10;i++) printf("%d ", koraciPrvog[ i ] ); //putchar('\n'); //for(int i = 0 ; i<10;i++) printf("%d ", koraciDrugog[ i ] ); //putchar('\n'); int i = 1; while( i ++ ) if(koraciPrvog[i] != koraciDrugog[i]) { int trazeni = i-1; if( koraciPrvog[ trazeni ] == x || koraciPrvog[ trazeni ] == y ) trazeni --; if( trazeni < 0 ) printf("Nemaju zajednickog\n"); else printf("%d\n",koraciPrvog[trazeni]); break; } } return 0; }