Pagini recente » Cod sursa (job #3005239) | Cod sursa (job #2562464) | Cod sursa (job #2410869) | Cod sursa (job #2561744) | Cod sursa (job #920521)
Cod sursa(job #920521)
#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;
}