Cod sursa(job #920521)

Utilizator razvan.popaPopa Razvan razvan.popa Data 20 martie 2013 15:36:16
Problema Lowest Common Ancestor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include<cstdio>
#include<list>
#include<algorithm>
#define pb push_back
#define nxt (*it)
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define ALL(g)\
   for(typeof(g.begin()) it=g.begin(); it!=g.end(); ++it)
#define infile "maimute.in"
#define outfile "maimute.out"
#define nMax 100005
#define logMax 20
using namespace std;

int E[nMax << 1], L[nMax << 1], P[nMax];

int Log[nMax << 1];

int DP[logMax][nMax << 2];

list < int > v[nMax];

int N, M;


void DF(int x, int lev, int tx){
    E[P[x] = ++E[0]] = x;
    L[E[0]] = lev;

    ALL(v[x])
        if(nxt != tx){
            DF(nxt, lev + 1, x);

            E[++E[0]] = x;
            L[E[0]] = lev;
        }
}

void RMQ(){
    FOR(i,2,E[0])
       Log[i] = Log[i >> 1] + 1;
    FOR(i,1,E[0])
       DP[0][i] = i;

    FOR(i,1,Log[E[0]])
       FOR(j,1, E[0] - (1<<i)){
           DP[i][j] = DP[i-1][j];
           if(L[DP[i-1][j + (1<<(i-1))]] < L[DP[i][j]])
              DP[i][j] = DP[i-1][j + (1<<(i-1))];
       }
}

int LCA(int x, int y){
    int px = P[x], py = P[y];

    int k = Log[py - px +1];

    int rez = DP[k][px];

	if(rez > L[DP[k][py - (1 << k) + 1]])
		rez = DP[k][py - (1 << k) + 1];

	return E[rez];
}

int main(){
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &N);

    int x, y;
    FOR(i,1,N-1){
        scanf("%d %d", &x, &y);

        v[x].pb(y);
        v[y].pb(x);
    }

    DF(1,0,0);

    RMQ();

    for(scanf("%d", &M); M; M--){
        scanf("%d %d", &x, &y);

        if(P[x] > P[y])
           swap(x, y);

        if(LCA(x,y) == x)
           puts("DA");
        else
           puts("NU");
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}